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

[ Video ] [ Powerpoint ]

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

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

PMSP - Expander graphs: Applications and combinatorial constructions

Workshop on Pseudorandomness in Mathematical Structures - June 15, 2010

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

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 ]

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 ]

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

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 ]

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 introductionfor computer scientists (optimization and complexity)

A talk given at the workshop "Algebraic Methods", Berkeley, California - December 3, 2018

[ Powerpoint ] [ Video ]

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

[ Powerpoint ] [ Video ]

Proving Algebraic Identities

The second of a 3-lecture series given at the Joint Mathematics Meetings, San Diego, California - January 11, 2018

[ Powerpoint ] [ Video ]

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

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

Analysis and Beyond - Celebrating Jean Bourgain's Work and Impact

Matrix and operator scaling: Analysis in the service of Algebra, Combinatorics, Geometry and more...

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

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 - Part 1 ] [ Video - Part 2 ]

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