- About
- Events
- Calendar
- Graduation Information
- Cornell Tech Colloquium
- Student Colloquium
- BOOM
- CS Colloquium
- Conway-Walker Lecture Series
- Salton Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University High School Programming Contest
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- Research Night
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- Admissions
- Current Students
- Field of Computer Science Ph.D. Student Handbook
- Ph.D. Requirements
- Business Card Policy
- Computer Science Graduate Office Hours
- Cornell Tech
- Curricular Practical Training
- Exam Scheduling Guidelines
- Fellowship Opportunities
- Field A Exam Summary Form
- Graduate School Forms
- Ph.D. Student Financial Support
- Special Committee Selection
- The Outside Minor Requirement
- Travel Funding Opportunities
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Groups
- Student Spotlights
- Contact PhD Office
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 address two important facets of this question: derandomizing small-space algorithms and constant-depth circuits. I will highlight a new technique---"iterative simplification"---for building more powerful pseudorandom generators (PRGs) from simpler ones leading up to nearly-optimal PRGs that overcome several longstanding bottlenecks within the above classes.
Raghu Meka received his PhD at UT Austin under the guidance of David Zuckerman. After that, he spent two years in Princeton as a postdoctoral fellow at the Institute for Advanced Study with Avi Wigderson and at DIMACS, Rutgers. Following that, he spent a year as a researcher at Microsoft Research, Silicon Valley Lab. He is currently an Assistant Professor in the Computer Science Department at UCLA. He is broadly interested in complexity theory, learning, and probability theory.