Talks

Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?). A 3-hour survey.
MIMUW Lecture Series - October 8, 2021
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
Computation Complexity Conference 2021 - July 20, 2021
Imitation Games
Public Lecture, Institute for Advanced Study, Princeton, NJ - May 6, 2021
The Value of Errors in Proofs - the fascinating journey from Turing's 1936 R ≠ RE to the 2020 breakthrough of MIP* = RE
Institute for Advanced Study, Princeton, NJ - March 1, 2021; Heidelberg Laureate Forum, Lausanne, CH - Sept 20, 2021
The Value of Errors in Proofs - a high level overview
StarkWare Industries, STARK @ Home XVII - January 07, 2021
The Impact of Cryptographic Thinking on TCS and Beyond
TCC Virtual Conference - November 16, 2020
An Introductory Survey on Expanders and Their Applications
Institute for Advanced Study, Princeton, NJ - September 29, 2020
Optimization, Complexity and Math
Harvard University, Mathematical Picture Language Seminar - September 15, 2020
[ Video ]
Games Computers (and computer scientists) Play
Game Theory 2020 - June 16, 2020
Non-commutative Optimization: Theory, Algorithms and Applications (or, can we prove P!=NP using gradient descent)
Institute for Advanced Study, Princeton, NJ - April 21, 2020
Optimization, Complexity and Math (or, can we prove P != NP using Gradient Descent)
Knuth Prize Lecture, STOC 2019 - June 25, 2019
[ Video ]
The sum-product theorem and applications
June 31, 2019
Invariant theory - a gentle introduction for computer scientists (optimization and complexity)
Algebraic Methods Workshop, Simons Institute, Berkeley, CA - December 3, 2018
Proving Analytic Inequalities
Joint Mathematics Meetings, San Diego, California - January 12, 2018
Proving Algebraic Identities
Joint Mathematics Meetings, San Diego, California - January 11, 2018
Alternate Minimization & Scaling Algorithms:Theory, Applications, Connections
Joint Mathematics Meetings, San Diego, California - January 10, 2018
Elementary open problems in Algebra (with consequences in computational complexity)
Institute for Advanced Study, Princeton, New Jersey - October 3, 2017
[ Video ]
Randomness
Berlin Mathematical School, Berlin, Germany - June 30, 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
CCC'17 Tutorial - Operator scaling: theory, applications and connections
Computational Complexity Conference 2017 - July 6 - 8, 2017
Some of My Favorite Open Problems on Expanders and Extractors
"Expanders and Extractors" workshop, Berkeley, California - January 31, 2017
[ Video ]
Matrix and operator scaling: Analysis in the service of Algebra, Combinatorics, Geometry and more...
Analysis and Beyond: Celebrating Jean Bourgain’s Work and Impact, IAS, Princeton, NJ - May 23, 2016
P vs. NP Problem: Efficient Computation...Knowledge
Institute for Advanced Study, Princeton, New Jersey - May 16, 2016
[ Video ]
The Resolution proof system
March 22, 2016
[ Video ]
Proof complexity - an introduction
March 15, 2016
[ Video ]
The singularity of symbolic matrices
February 8, 9 & 16, 2016
Elementary mathematical problems implying computational hardness
Noga Alon's 60th birthday conference, Tel Aviv, Israel - January 20, 2016
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Michael Forbes - January 19, 2016
[ Video ]
Perfect Matchings and Symbolic Matrices
A talk in honor of Dick Karp's 80th birthday, Berkeley, California - October 17, 2015
More on sum-of-squares proofs for planted clique
December 9, 2014 (continuation of "Sum-of-squares lower bounds for the planted clique problem" )
[ Video ]
Sum-of-squares lower bounds for the planted clique problem
November 25, 2014 (continued in "More on sum-of-squares proofs for planted clique")
[ Video ]
Michael Sipser's 60th Birthday
A talk given at the Symposium on Theoretical Computer Science, MIT, Cambridge, MA - October 26, 2014
Permanent and Determinant: Non-identical Twins
A lecture given for the 2014 Green Family Lectures at IPAM, Los Angeles, California - May 20, 2014
Randomness and Pseudorandomness
A lecture given for the 2014 Green Family Lectures at IPAM, Los Angeles, California - May 19, 2014
[ Video ]
Non-commutative arithmetic computation
February 11 & 18, 2014
In search of explicit matrices that behave like random ones
February 7, 2014
[ Video ]
Non-commutative computation with division
A lecture given at ITCS, Princeton, New Jersey - January 12, 2014
Nati's Long View
Nati Linial's 60'th birthday conference, Jerusalem, Israel - December 18, 2013
Structure in TCS
Simons Symposium on Visions of the Theory of Computing - May 31, 2013
Derandomization of Probabilistic Logspace (The Nisan Variations)
March 5, 2013 (continuation of "Derandomizing BPL?")
[ Video ]
Derandomizing BPL?
February 26, 2013 (continued in "Derandomization of Probabilistic Logspace (The Nisan Variations)")
[ Video ]
The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System Series
December 18, 2012
[ Video ]
Randomness - the Utility of Unpredictability
The Wolfgang Pauli Lectures 2012 - May 10, 2012
[ Video ]
Cryptography: Secrets and Lies, Knowledge and Trust
The Wolfgang Pauli Lectures 2012 - May 8, 2012
[ Video ]
The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits to Human Knowledge
The Wolfgang Pauli Lectures 2012 - May 7, 2012
[ Video ]
Local Correction of Codes and Euclidean Incidence Geometry
March 5, 2012
[ Video ]
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 ]
Randomness Extractors - Applications and Constructions
Restriction Access
A talk given at the Analysis of Algorithms 2012
The power and weakness of randomness (when you are short on time)
November 10, 2011
Randomness and Pseudo-randomness
October 5, 2011
[ Video ]
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
Workshop on Pseudorandomness in Mathematical Structures - June 15, 2010
Expander graphs - applications and combinatorial constructions
A 3-hour tutorial, Pseudorandomness in Mathematical Structures Workshop, IAS, Princeton, NJ - June 14-18, 2010
The Stepanov Method
Institute for Advanced Study, Princeton, New Jersey - May 25, 2010
[ Video ]
Expanders, Groups and Representations
Laci Babai's 60th Birthday Celebration, Columbus, OH - March 21-25, 2010
Representation Theory and Expansion in Groups
January 26, February 2 & 9, 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
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
Quarter-century of proofs of the XOR lemma
(skeleton of a lecture)
Pseudorandomness - Randomness extractors
Pseudorandomness in Mathematics and Computer Science Mini-Workshop - December 3, 2008
[ Video ]
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
Algebrization: A New Barrier in Complexity Theory
Theory Seminar, CS Department, UC Berkeley - November 5, 2008
The "P vs. NP" Problem
Public Lecture at the Institute for Advanced Study - October 24, 2008
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
Cryptography: secrets and lies, knowledge and trust - Lecture III
Time, space and the cosmology of computational problems - Lecture II
Algorithms: a common language for nature, man and computer - Lecture I
Kurt Gödel and Computer Science
A talk given at the Goedel Centenary at the IAS - November 17, 2006
Lecture I - Algorithms: a common language for nature, man and computer
Louis Clark Vanuxem Lecture: A Worldview through the Computational Lens
Talks given at Princeton University for the Louis Clark Vanuxem Lecture (cosponsored by Princeton University Press), February 13, 2006
[ Video ]
Lecture II - Time, space and the cosmology of computational problems
Louis Clark Vanuxem Lecture: A Worldview through the Computational Lens
Talks given at Princeton University for the Louis Clark Vanuxem Lecture (cosponsored by Princeton University Press), February 13, 2006
[ Video ]
Lecture III - Cryptography: secrets and lies, knowledge and trust
Louis Clark Vanuxem Lecture: A Worldview through the Computational Lens
Talks given at Princeton University for the Louis Clark Vanuxem Lecture (cosponsored by Princeton University Press), February 13, 2006
[ Video ]
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 ]
Randomness, Games and Computers
School of Mathematics 75th Anniversary - March 11, 2005
[ Video ]
Depth through breadth (or why should we listen to talks in other areas)
Talk given at STOC 2014 - June 13-15, 2004
Expander graphs - where combinatorics and algebra compete and cooperate
(more algebraic than the survey below)
Zigzag product, expander constructions, connections and applications
(more applications than the survey above)
The digital envelope - a crash course in modern cryptography
This lecture, part of the Institute’s 1999-2000 Faculty Lecture Series, was intended for a general audience and was open to the public - March 29, 2000
Complexity insight