Skip to main content

Avi Wigderson

Personal
Works
Post-Docs
Students
CSDM
- Seminars
Conferences & videos

You are here

Home » Avi Wigderson

Talks

Submitted by charlie on Wed, 2012-01-25 08:55

Algorithms: a common language for nature, man and computer - Lecture I
The Value of Errors in Proofs - a high level overview
The Value of Errors in Proofs - the fascinating journey from Turing's 1936 R ≠ RE to the 2020 breakthrough of MIP* = RE
CCC'17 Tutorial - Operator scaling: theory, applications and connections
Games Computers (and computer scientists) Play
Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?). A 3-hour survey.
Optimization, Complexity and Math
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
Time, space and the cosmology of computational problems - Lecture II
Cryptography: secrets and lies, knowledge and trust - Lecture III
A Survey of Lower Bounds for the Resolution Proof System
Algebrization: A New Barrier in Complexity Theory
An Introductory Survey on Expanders and Their Applications
An introductory survey on expanders and their applications
Avi Wigderson (with Karl Jalochowski), Life Is Beautiful, 2014
Avi Wigderson talking with Alon Rosen about Complexity Theory and PCP, 2019
Complexity insight
Conversation between Christos Papadimitriou and Avi Wigderson on TOC, 2019
Cryptography: Secrets and Lies, Knowledge and Trust
Depth through breadth (or why should we listen to talks in other areas)
Derandomization of Probabilistic Logspace (The Nisan Variations)
Derandomizing BPL?
Direct product testing, parallel repetition and foams
Direct-product testing, and a new 2-query PCP
Elementary mathematical problems implying computational hardness
Elementary open problems in Algebra (with consequences in computational complexity)
Expander graphs - applications and combinatorial constructions
Expander graphs - where combinatorics and algebra compete and cooperate
Expander graphs: Applications and combinatorial constructions
Expanders, Groups and Representations
In search of explicit matrices that behave like random ones
Invariant theory - a gentle introduction for computer scientists (optimization and complexity)
Kurt Gödel and Computer Science
Kurt Gödel, von Neumann, and Theoretical Computer Science
Lecture I - Algorithms: a common language for nature, man and computer
Lecture II - Time, space and the cosmology of computational problems
Lecture III - Cryptography: secrets and lies, knowledge and trust
Les Valiant's Permanent Gift to Theoretical Computer Science
Local Correction of Codes and Euclidean Incidence Geometry
Matrix and operator scaling: Analysis in the service of Algebra, Combinatorics, Geometry and more...
Michael Sipser's 60th Birthday
More on sum-of-squares proofs for planted clique
Nati's Long View
Non-commutative Optimization: Theory, Algorithms and Applications (or, can we prove P!=NP using gradient descent)
Non-commutative arithmetic computation
Non-commutative computation with division
On the nature and future of the Theory of Computation (ToC)
Optimization, Complexity and Math (or, can we prove P != NP using Gradient Descent)
P vs. NP Problem: Efficient Computation...Knowledge
Perfect Matchings and Symbolic Matrices
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Proof complexity - an introduction
Proof, Computation and Randomness
Proving Algebraic Identities
Proving Analytic Inequalities
Pseudorandomness - Randomness extractors
Quarter-century of proofs of the XOR lemma
Randomness - the Utility of Unpredictability
Randomness -- A computational complexity view
Randomness
Randomness Extractors - Applications and Constructions
Randomness and Pseudo-randomness
Randomness, Games and Computers
Representation Theory and Expansion in Groups
Science Lives with Endre Szemerédi, Simons Foundation, 2013
Science Lives with László Lovász, Simons Foundation, 2013
Seeded Randomness Extractors: applications and constructions
Some of My Favorite Open Problems on Expanders and Extractors
Structure in TCS
Sum-of-squares lower bounds for the planted clique problem
Technion Honorary Doctorate, 2023
The "P vs. NP" Problem
The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits to Human Knowledge
The Abel Prize, 2021
The Art of Reduction (or Depth through Breadth)
The Resolution proof system
The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System Series
The Stepanov Method
The art of reduction
The digital envelope - a crash course in modern cryptography
The singularity of symbolic matrices
The sum-product theorem and applications
Theoretical Computer Science Methods in Asymptotic Geometry
Women in Theory (of Computer Science) - I Will Survive!, 2020
Zero Knowledge Proof (with Brady Haran) - Numberphile, 2021
Zigzag product, expander constructions, connections and applications

‹ Szemeredi and TCS up Algorithms: a common language for nature, man and computer - Lecture I ›