Limit Theorems in Pseudorandomness and Learning Theory

Опубликовано 17 августа 2016, 0:37

An important theme in theoretical computer science over the last decade has been the usefulness of translating a combinatorial problem over a discrete domain to a problem in continuous space. For instance, invariance principles or classical limit theorems from probability have played a crucial role in recent breakthroughs in hardness of approximation and social choice theory. In this talk, I will present results which develop this high-level approach further by building a generic theory for applying invariance principles to problems in pseudorandomness and learning theory. On the pseudorandomness side, I will describe a generic framework for obtaining pseudorandom generators (PRGs) from limit theorems, leading to the best known PRGs for various natural geometric concept classes such as halfspaces, polynomial threshold functions, polytopes and combinatorial shapes. On the learning-theoretic side, I will briefly outline the use of invariance principles in developing the best algorithms for agnostically learning polynomial threshold functions and intersections of regular halfspaces.