Cryptography: Secrets and Lies, Knowledge and Trust
Virtual Technion Lecture - September 16, 2024
ACM Turing Award Lecture
ACM STOC, Vancouver, Canada - June 27, 2024
Elementary Problems of Computational Significance
Tim Gowers' 60th Birthday Conference, Isaac Newton Institute, Cambridge, UK - April 10, 2024
Faster Parallel Algorithms for Basic Linear Algebra Problems
A Workshop in Honor of Michael Ben-Or, Berkeley, CA - March 25, 2024
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
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
The sum-product theorem and applications
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
Randomness
Berlin Mathematical School, Berlin, Germany - June 30, 2017
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
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
The Resolution proof system
Proof complexity - an introduction
The singularity of symbolic matrices
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
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" )
Sum-of-squares lower bounds for the planted clique problem
November 25, 2014 (continued in "More on sum-of-squares proofs for planted clique")
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
Non-commutative arithmetic computation
In search of explicit matrices that behave like random ones
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?")
Derandomizing BPL?
February 26, 2013 (continued in "Derandomization of Probabilistic Logspace (The Nisan Variations)")
The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System Series
Randomness - the Utility of Unpredictability
The Wolfgang Pauli Lectures 2012 - May 10, 2012
Cryptography: Secrets and Lies, Knowledge and Trust
A talk given for the Wolfgang Pauli Lectures, Zurich, Switzerland - May 8, 2012
The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits to Human Knowledge
The Wolfgang Pauli Lectures 2012 - May 7, 2012
Local Correction of Codes and Euclidean Incidence Geometry
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
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)
Randomness and Pseudo-randomness
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
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
Pseudorandomness - Randomness extractors
Pseudorandomness in Mathematics and Computer Science Mini-Workshop - December 3, 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
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
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
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
Kurt Gödel, von Neumann, and Theoretical Computer Science
A talk given at the 75th anniversary of the School of Mathematics at the IAS.
Randomness, Games and Computers
School of Mathematics 75th Anniversary - March 11, 2005
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