Talks

Non-commutative optimization: theory, algorithms and applications (or, can we prove P!=NP using gradient descent)
A talk given at the Institute for Advanced Study, as part of the CSDM seminars - April 21, 2020
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
Randomness, Games and Computers
School of Mathematics 75th Anniversary - March 11, 2005
[ Video ]
Pseudorandomness - Randomness extractors
Pseudorandomness in Mathematics and Computer Science Mini-Workshop - December 3, 2008
[ Video ]
Representation Theory and Expansion in Groups
January 26, February 2 & 9, 2010
The Stepanov Method
May 25, 2010
[ Video ]
PMSP - Expander graphs: Applications and combinatorial constructions
Workshop on Pseudorandomness in Mathematical Structures - June 15, 2010
Randomness and Pseudo-randomness
October 5, 2011
[ Video ]
CSDM: A Survey of Lower Bounds for the Resolution Proof System
January 31, 2012
[ Video ]
Local Correction of Codes and Euclidean Incidence Geometry
March 5, 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 ]
Cryptography: Secrets and Lies, Knowledge and Trust
The Wolfgang Pauli Lectures 2012 - May 8, 2012
[ Video ]
Randomness - the Utility of Unpredictability
The Wolfgang Pauli Lectures 2012 - May 10, 2012
[ Video ]
The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System Series
December 18, 2012
[ Video ]
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 ]
In search of explicit matrices that behave like random ones
February 7, 2014
[ Video ]
Non-commutative arithmetic computation
February 11 & 18, 2014
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 ]
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 ]
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Michael Forbes - January 19, 2016
[ Video ]
The singularity of symbolic matrices
February 8, 9 & 16, 2016
Proof complexity - an introduction
March 15, 2016
[ Video ]
The Resolution proof system
March 22, 2016
[ 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 - May 23, 2016
[ Video ]
On the nature and future of the Theory of Computation (ToC)
June 20, 2017
[ Video ]
CCC'17 Tutorial - Operator scaling: theory, applications and connections
Computational Complexity Conference 2017 - July 6 - 8, 2017
Optimization, Complexity and Math (or, can we prove P != NP using Gradient Descent)
Knuth Prize Lecture, STOC 2019 - June 25, 2019
[ Video ]
Invariant theory- a gentle introduction for computer scientists (optimization and complexity)
A talk given at the workshop "Algebraic Methods", Berkeley, California - December 3, 2018
Randomness
A talk given at the Berlin Mathematical School, Berlin, Germany - June 30, 2017
[ Video ]
Proving Analytic Inequalities
The third of a 3-lecture series given at the Joint Mathematics Meetings, San Diego, California - January 12, 2018
Proving Algebraic Identities
The second of a 3-lecture series given at the Joint Mathematics Meetings, San Diego, California - January 11, 2018
Alternate Minimization & Scaling Algorithms:Theory, Applications, Connections
The first of a 3-lecture series given at the Joint Mathematics Meetings, San Diego, California - January 10, 2018
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 ]
Analysis and Beyond - Celebrating Jean Bourgain's Work and Impact
Matrix and operator scaling: Analysis in the service of Algebra, Combinatorics, Geometry and more...
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 "P vs. NP" 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 insight
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
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