Talks

A Survey of Lower Bounds for the Resolution Proof System
A 2-hour survey given at the Institute for Advanced Study, Princeton, New Jersey - January 31, 2012
[ Video ]
"The Stepanov Method"
A 2-hour talk given at the Institute for Advanced Study, Princeton, New Jersey - May 25, 2010
[ Video ]
"Elementary open problems in Algebra (with consequences in computational complexity)"
A talk given at the Institute for Advanced Study, Princeton, New Jersey - October 3, 2017
[ Video ]
"On the nature and future of the Theory of Computation (ToC)"
A Keynote Lecture given at the Symposium on the Theory of Computing, Montreal, Candada - June 20, 2017
"P vs. NP" Problem: Efficient Computation...Knowledge
A talk given at the Institute for Advanced Study, Princeton, New Jersey - May 16, 2016
[ Video ]
"Some of My Favorite Open Problems on Expanders and Extractors"
A talk given at the workshop "Expanders and Extractors", Berkeley, California - January 31, 2017
[ Video ]
"Matrix & Operator scaling and their many applications"
A talk given at the conference "Analysis and beyond", celebrating Jean Bourgain's work and impact, IAS, Princeton, New Jersey - May 23, 2016
"Elementary mathematical problems implying computational hardness"
A talk given at Noga Alon's 60th birthday conference, Tel Aviv, Israel - January 20, 2016
"Perfect Matchings and Symbolic Matrices"
A talk in honor of Dick Karp's 80th birthday, Berkeley, California - October 17, 2015
"Michael Sipser's 60th Birthday"
A talk given at the Symposium on Theoretical Computer Science, MIT, Cambridge, MA - October 26, 2014
"Randomness and Pseudorandomness"
A lecture given for the 2014 Green Family Lectures at IPAM, Los Angeles, California - May 19, 2014
[ Video ]
"Permanent and Determinant: Non-identical Twins"
A lecture given for the 2014 Green Family Lectures at IPAM, Los Angeles, California - May 20, 2014
[ Video ]
"Non-commutative computation with division"
A lecture given at ITCS, Princeton, New Jersey - January 12, 2014
"Nati Long View"
A talk given at Nati Linial's 60'th birthday conference, Jerusalem, Israel - December 18, 2013
"Structure in TCS"
A talk given at the Simons Symposium on Visions of the Theory of Computing, May 31, 2013
"Restriction Access"
A talk given at the Analysis of Algorithms 2012
"Randomness and Pseudorandomness"
A talk given for the Friends Forum at the Institute for Advanced Study, Princeton, New Jersey - October 5, 2011
"Szemeredi and TCS"
Endre Szemeredi's 70th birthday conference, Budapest, August 2-6, 2010
"Expander graphs - applications and combinatorial constructions"
A 3-hour tutorial, Pseudorandomness in Mathematical Structures Workshop, IAS, Princeton, NJ - June 14-18, 2010
"Expanders, Groups and Representations"
Laci Babai's 60th Birthday Celebration, Columbus, OH - March 21-25, 2010
"Direct product testing, parallel repetition and foams"
Analytical Methods in Combinatorics, Additive Number Theory and Computer Science Workshop, IPAM, UCLA - December 1-4, 2009
"Quarter-century of proofs of the XOR lemma"
(skeleton of a lecture)
"Theoretical Computer Science Methods in Asymptotic Geometry"
Vitali Milman's 70th Birthday Celebration, Tel Aviv, Israel - June 24, 2009
"Les Valiant's Permanent Gift to Theoretical Computer Science"
60th Birthday Celebration, Bethesda, MD - May 30, 2009
"Direct-product testing, and a new 2-query PCP"
Theory Seminar, CS Department, Technion - Israel Institute of Technology, Haifa, Israel - March 1, 2009
"Seeded Randomness Extractors: applications and constructions"
Princeton University Discrete Math Seminar - February 19, 2009
"Algebrization: A New Barrier in Complexity Theory"
Theory Seminar, CS Department, UC Berkeley - November 5, 2008
"Randomness -- A computational complexity view"
Logic Seminar at Penn State University, State College, PA - November 20, 2008
"The Art of Reduction (or Depth through Breadth)"
Distinguished Lecturer Series at Penn State University, State College, PA - November 19, 2008
"The PvsNP Problem"
Public Lecture at the Institute for Advanced Study - October 24, 2008
"The sum-product theorem and applications"
"Proof, Computation and Randomness"
at National Science Foundation, Arlington, VA - September 27, 2007.
"The art of reduction"
Keynote lecture at FCRC, San Diego, CA - June 13, 2007
"Expander graphs - where combinatorics and algebra compete and cooperate"
(more algebraic than the survey above)
"Zigzag product, expander constructions, connections and applications"
(more applications than the survey below)
"Complexity insights"
"Depth through breadth (or why should we listen to talks in other areas)
"The digital envelope - a crash course in modern cryptography"
"Games computers (and computer scientists) play"
"The power and weakness of randomness (when you are short on time)"
"Randomness Extractors - Applications and Constructions"
"Kurt Gödel, von Neumann, and Theoretical Computer Science"
A talk given at the 75th anniversary of the School of Mathematics at the IAS.
[ Powerpoint ] [ RM ]
"Kurt Gödel and Computer Science,"
A talk given at the Goedel Centenary at the IAS - November 17, 2006
[ Video ]
Louis Clark Vanuxem Lectures
"Algorithms: a common language for nature, man and computer" Lecture I
"Time, space and the cosmology of computational problems" Lecture II
"Cryptography: secrets and lies, knowledge and trust" Lecture III