Limit Theorems in Pseudorandomness and Learning Theory

January 20, 2011
Raghu Meka | University of Texas at Austin

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.

발표자 세부 정보

Raghu Meka is a PhD student in computer science at the University of Texas at Austin advised by Prof. David Zuckerman. He is a recipient of the Dean’s Excellence award and MCD fellowship at UT Austin. Prior to joining UT Austin, he completed his B.Tech from Indian Institute of Technology, Chennai, India.