IC Colloquium : Structure and Geometry of Randomness
Event details
| Date | 25.02.2013 |
| Hour | 16:15 › 17:30 |
| Speaker |
Raghu Meka, Institute for Advanced Study, Princeton and DIMACS, Rutgers University IC faculty candidate |
| Location | |
| Category | Conferences - Seminars |
Abstract
The use of randomness is fundamental in algorithms and complexity theory. However, in spite of the prevalence of randomized algorithms, it is still unknown if randomness is essential for the design of efficient algorithms. This is one of the foremost open problems in computer science. In this talk I will explain new approaches to various important cases of the problem that are motivated by classical results in probability such as the central limit theorem.
As an example of this approach I will describe a central limit theorem for polytopes and how it relates to problems in pseudo-randomness and learning theory, emphasizing the deep connections between these seemingly disparate areas.
Biography
Raghu Meka is currently a postdoctoral fellow at the Institute for Advanced Study, Princeton and DIMACS, Rutgers. He received his PhD from the department of computer science at the University of Texas at Austin in 2011. He is a recipient of the Bert Kay best dissertation award, the Dean's Excellence award and an MCD fellowship at UT Austin. Prior to joining UT Austin, he completed his B.Tech in computer science from Indian Institute of Technology, Chennai, India. His main interests are in complexity theory, pseudo-randomness, algorithm design, learning theory and data mining.
The use of randomness is fundamental in algorithms and complexity theory. However, in spite of the prevalence of randomized algorithms, it is still unknown if randomness is essential for the design of efficient algorithms. This is one of the foremost open problems in computer science. In this talk I will explain new approaches to various important cases of the problem that are motivated by classical results in probability such as the central limit theorem.
As an example of this approach I will describe a central limit theorem for polytopes and how it relates to problems in pseudo-randomness and learning theory, emphasizing the deep connections between these seemingly disparate areas.
Biography
Raghu Meka is currently a postdoctoral fellow at the Institute for Advanced Study, Princeton and DIMACS, Rutgers. He received his PhD from the department of computer science at the University of Texas at Austin in 2011. He is a recipient of the Bert Kay best dissertation award, the Dean's Excellence award and an MCD fellowship at UT Austin. Prior to joining UT Austin, he completed his B.Tech in computer science from Indian Institute of Technology, Chennai, India. His main interests are in complexity theory, pseudo-randomness, algorithm design, learning theory and data mining.
Links
Practical information
- Informed public
- Free
- This event is internal
Contact
- Christine Moscioni