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

[ Powerpoint ] [ Video ]

"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

[ Powerpoint ]

"Elementary mathematical problems implying computational hardness"

A talk given at Noga Alon's 60th birthday conference, Tel Aviv, Israel - January 20, 2016

[ Powerpoint ]

"Perfect Matchings and Symbolic Matrices"

A talk in honor of Dick Karp's 80th birthday, Berkeley, California - October 17, 2015

[ Powerpoint ]

"Michael Sipser's 60th Birthday"

A talk given at the Symposium on Theoretical Computer Science, MIT, Cambridge, MA - October 26, 2014

[ Powerpoint ]

"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

[ Powerpoint ]

"Nati Long View"

A talk given at Nati Linial's 60'th birthday conference, Jerusalem, Israel - December 18, 2013

[ Powerpoint ]

"Structure in TCS"

A talk given at the Simons Symposium on Visions of the Theory of Computing, May 31, 2013

[ Powerpoint ] [ Video ]

"Randomness and Pseudorandomness"

A talk given for the Friends Forum at the Institute for Advanced Study, Princeton, New Jersey - October 5, 2011

[ Powerpoint ] [ Video ]

"Szemeredi and TCS"

Endre Szemeredi's 70th birthday conference, Budapest, August 2-6, 2010

[ Powerpoint ]

"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

[ Powerpoint ]

"Direct product testing, parallel repetition and foams"

Analytical Methods in Combinatorics, Additive Number Theory and Computer Science Workshop, IPAM, UCLA - December 1-4, 2009

[ Powerpoint ]

"Theoretical Computer Science Methods in Asymptotic Geometry"

Vitali Milman's 70th Birthday Celebration, Tel Aviv, Israel - June 24, 2009

[ Powerpoint ]

"Les Valiant's Permanent Gift to Theoretical Computer Science"

60th Birthday Celebration, Bethesda, MD - May 30, 2009

[ Powerpoint ]

"Direct-product testing, and a new 2-query PCP"

Theory Seminar, CS Department, Technion - Israel Institute of Technology, Haifa, Israel - March 1, 2009

[ Powerpoint ]

"Seeded Randomness Extractors: applications and constructions"

Princeton University Discrete Math Seminar - February 19, 2009

[ Powerpoint ]

"Algebrization: A New Barrier in Complexity Theory"

Theory Seminar, CS Department, UC Berkeley - November 5, 2008

[ Powerpoint ]

"Randomness -- A computational complexity view"

Logic Seminar at Penn State University, State College, PA - November 20, 2008

[ Powerpoint ]

"The Art of Reduction (or Depth through Breadth)"

Distinguished Lecturer Series at Penn State University, State College, PA - November 19, 2008

[ Powerpoint ]

"The PvsNP Problem"

Public Lecture at the Institute for Advanced Study - October 24, 2008

[ Powerpoint ]

"Proof, Computation and Randomness"

at National Science Foundation, Arlington, VA - September 27, 2007.

[ Powerpoint ]

"Expander graphs - where combinatorics and algebra compete and cooperate"

(more algebraic than the survey above)

[ Powerpoint ]

"Zigzag product, expander constructions, connections and applications"

(more applications than the survey below)

[ Powerpoint ]

"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 ]

"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