Elementary Problems of Computational Significance

Tim Gowers' 60th Birthday Conference, Isaac Newton Institute, Cambridge, UK - April 10, 2024

[ Powerpoint ]

Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?). A 3-hour survey.

MIMUW Lecture Series - October 8, 2021

[ Powerpoint ] [ Video ]

Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Computation Complexity Conference 2021 - July 20, 2021

[ Powerpoint ] [ Video ]

Imitation Games

Public Lecture, Institute for Advanced Study, Princeton, NJ - May 6, 2021

[ Powerpoint ] [ Video ]

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

[ Powerpoint ] [ Video ]

The Impact of Cryptographic Thinking on TCS and Beyond

TCC Virtual Conference - November 16, 2020

[ Powerpoint ] [ Video ]

An Introductory Survey on Expanders and Their Applications

Institute for Advanced Study, Princeton, NJ - September 29, 2020

[ Powerpoint ] [ Video ]

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

[ Powerpoint ] [ Video - HEBREW ]

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

[ Powerpoint ] [ Video ]

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)

Algebraic Methods Workshop, Simons Institute, Berkeley, CA - December 3, 2018

[ Powerpoint ] [ Video ]

Proving Analytic Inequalities

Joint Mathematics Meetings, San Diego, California - January 12, 2018

[ Powerpoint ] [ Video ]

Proving Algebraic Identities

Joint Mathematics Meetings, San Diego, California - January 11, 2018

[ Powerpoint ] [ Video ]

Alternate Minimization & Scaling Algorithms:Theory, Applications, Connections

Joint Mathematics Meetings, San Diego, California - January 10, 2018

[ Powerpoint ] [ Video ]

Elementary open problems in Algebra (with consequences in computational complexity)

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 ]

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

[ Powerpoint ] [ Video ]

P vs. NP Problem: Efficient Computation...Knowledge

Institute for Advanced Study, Princeton, New Jersey - May 16, 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

[ Powerpoint ]

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

[ Powerpoint ]

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

[ Powerpoint ]

Permanent and Determinant: Non-identical Twins

A lecture given for the 2014 Green Family Lectures at IPAM, Los Angeles, California - May 20, 2014

[ Powerpoint ] [ Video ]

Randomness and Pseudorandomness

A lecture given for the 2014 Green Family Lectures at IPAM, Los Angeles, California - May 19, 2014

[ Video ]

Non-commutative computation with division

A lecture given at ITCS, Princeton, New Jersey - January 12, 2014

[ Powerpoint ]

Nati's Long View

Nati Linial's 60'th birthday conference, Jerusalem, Israel - December 18, 2013

[ Powerpoint ]

Structure in TCS

Simons Symposium on Visions of the Theory of Computing - May 31, 2013

[ Powerpoint ] [ 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 ]

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 ]

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 power and weakness of randomness (when you are short on time)

November 10, 2011

[ 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

Workshop on Pseudorandomness in Mathematical Structures - June 15, 2010

[ Video - Part 1 ] [ Video - Part 2 ]

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 ]

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

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

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

[ Powerpoint ]

The Art of Reduction (or Depth through Breadth)

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

[ Powerpoint ]

Algebrization: A New Barrier in Complexity Theory

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

[ Powerpoint ]

The "P vs. NP" Problem

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

[ Video ] [ Powerpoint ]

Proof, Computation and Randomness

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

[ Powerpoint ]

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

[ Video - Part 1 ] [ Video - Part 2 ]

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

[ Video ]

Lecture III - Cryptography: secrets and lies, knowledge and trust

Louis Clark Vanuxem Lecture: A Worldview through the Computational Lens

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

Depth through breadth (or why should we listen to talks in other areas)

Talk given at STOC 2014 - June 13-15, 2004

[ Powerpoint ]

Expander graphs - where combinatorics and algebra compete and cooperate

(more algebraic than the survey below)

[ Powerpoint ]

Zigzag product, expander constructions, connections and applications

(more applications than the survey above)

[ Powerpoint ]

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

[ Powerpoint ]