1:10:20
Extractor-based Approach to Proving Memory-Sample Lower Bounds for Learning - Sumegha Garg
Institute for Advanced Study
2:06:25
Getting the most from our data - Paul Valiant
1:08:15
Thresholds for Random Subspaces, aka, LDPC Codes Achieve List-Decoding Capacity - Mary Wootters
2:00:09
Factorization through L2, Rounding and Duality Part 2 - Vijay Bhattiprolu
1:11:20
New isoperimetric inequalities for convex bodies - Amir Yehudayoff
2:03:36
Factorization through L2, Rounding and Duality - Vijay Bhattiprolu
1:13:02
Indistinguishability Obfuscation from Well-Founded Assumptions - Huijia (Rachel) Lin
57:33
Associativity testing - Ben Green
1:04:42
Anti-concentration and the Gap-Hamming problem - Anup Rao
1:56:14
On the extension complexity of random polytopes - Lisa Sauermann
2:04:09
The threshold for the square of a Hamilton cycleJinyoung Park
1:11:58
A Parallel Repetition Theorem for the GHZ Game - Justin Holmgren
2:08:55
Arithmetic progressions and spectral structure - Thomas Bloom
1:15:45
Explicit near-fully X-Ramanujan graphs - Xinyu Wu
1:15:57
Splitting Necklaces: Existence, Hardness and ApproximationNoga Alon
1:58:58
An introductory survey on expanders and their applications - Avi Wigderson
1:31:28
Convex Set Disjointness, Distributed Learning of Halfspaces, and Linear Programming - Shay Moran
1:09:45
Using discrepancy theory to improve the design of randomized controlled trials - Daniel Spielman
1:57:36
Cutting Planes Proofs of Tseitin and Random Formulas - Noah Fleming
1:08:39
Local Statistics, Semidefinite Programming, and Community Detection - Prasad Raghavendra
2:02:40
A Framework for Quadratic Form Maximization over Convex Sets -Vijay Bhattiprolu
1:34:24
Graph and Hypergraph Sparsification - Luca Trevisan
1:58:29
Geodesically Convex Optimization (or, can we prove P!=NP using gradient descent) - Avi Wigderson
1:01:19
Structure vs Randomness in Complexity Theory - Rahul Santhanam
1:18:09
Legal Theorems of Privacy - Kobbi Nissim
1:56:56
Primality testing - Andrey Kupavskii
1:05:17
Borrowing memory that's being used: catalytic approaches to the Tree Evaluation Problem - James Cook
1:50:52
High dimensional expansion and agreement testing - Irit Dinur
53:38
CSPs with Global Modular Constraints: Algorithms and Hardness via... - Sivakanth Gopi
1:33:08
High dimensional expanders - Part 2 - Irit Dinur
1:52:04
Sharp Thresholds and Extremal Combinatorics - Dor Minzer
1:35:50
Feature purification: How adversarial training can perform robust deep learning - Yuanzhi Li
1:51:14
Introduction to high dimensional expanders - Irit Dinur
1:04:34
Learning from Censored and Dependent Data - Constantinos Daskalakis
1:50:02
An introduction to Boolean Function Analysis - Dor Minzer
1:02:32
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games... - Zhao Song
51:18
Spectral Independence in High-dimensional Expanders and Applications... - Kuikui Liu
1:43:42
Is the variety of singular tuples of matrices a null cone? - Viswambhara Makam
1:07:08
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
1:45:04
An invitation to invariant theory - Viswambhara Makam
1:59:01
Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory - Robert Robere
58:45
Paths and cycles in expanders - Michael Krivelevich
1:03:31
Explicit rigid matrices in P^NP via rectangular PCPs - Prahladh Harsha
1:53:33
Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory -Robert Robere
58:54
MIP* = RE - Henry Yuen
56:17
Equality Alone Does not Simulate Randomness- Marc Vinyals
1:09:17
Thresholds Versus Fractional Expectation-Thresholds - Keith Frankston
1:06:18
Graph Sparsification via Short Cycle Decomposition - Sushant Sachdeva
1:46:07
Regularity lemma and its applications Part I - Fan Wei
1:08:31
Rainbow fractional matchings - Ron Holzman
1:40:57
Constraint Satisfaction Problems and Probabilistic Combinatorics II - Fotios Illiopoulos
1:06:19
Lifting small locally testable codes (LTCs) to large LTCs via HDXs - Prahladh Harsha
1:49:52
Constraint Satisfaction Problems and Probabilistic Combinatorics I - Fotios Illiopoulos
1:11:16
An isoperimetric inequality for the Hamming cube and some consequences - Jinyoung Park
1:52:47
Extremal set theory II - Andrey Kupavskii
1:51:38
Extremal set theory - Andrey Kupavskii
1:01:40
Sparse matrices in sparse analysis - Anna Gilbert
1:00:31
Furstenberg sets in finite fields - Zeev Dvir
1:48:57
Towards a theory of non-commutative optimization...… -Rafael Oliveira
1:03:18
Learning arithmetic circuits in the average case via lower bounds - Ankit Garg
1:42:40
Asymptotic spectra and Applications II - Jeroen Zuiddam
1:07:34
Choiceless Polynomial Time - Ben Rossman
1:10:45
On the possibility of an instance-based complexity theory - Boaz Barak
1:11:10
Collective Coin-Flipping Protocols and Influences of Coalitions - Hamed Hatami
1:07:33
Fooling polytopes - Li-Yang Tan
1:52:59
Factors of sparse polynomials: structural results and some algorithms - Shubhangi Saraf
1:14:48
On the Approximation Resistance of Balanced Linear Threshold Functions - Aaron Potechin
1:45:46
A Brief Tour of Proof Complexity: Lower Bounds and Open Problems - Toniann Pitassi
1:01:22
An Application of the Universality Theorem for Tverberg Partitions - Imre Barany
2:02:12
Halting problems for sandpiles and abelian networks - Lionel Levine
1:03:09
Near log-convexity of measured heat in (discrete) time and consequences - Mert Sağlam
1:48:56
Improved List-Decoding and Local List-Decoding Algorithms for Polynomial Codes - Swastik Kopparty
1:11:42
Strongly log concave polynomials...Bases of Matroids - Shayan Oveis Gharan
1:37:54
Lorentzian Polynomials - June Huh
1:38:38
Why can't we prove tensor rank and Waring rank lower bounds? - Visu Makam
Non-commutative rank - Visu Makam
57:06
Near-Optimal Strong Dispersers - Dean Doron
1:57:05
A Regularity Lemma with Modifications - Guy Moshkovitz
59:23
PCP and Delegating Computation: A Love Story - Yael Tauman Kalai
1:33:15
New Results on Projections - Guy Moshkovitz
2:01:36
An invitation to tensor networks - Michael Walter
57:39
A matrix expander Chernoff bound - Ankit Garg
1:52:54
Monotone Circuit Lower Bounds from Resolution - Mika Goos
57:04
Classical Verification of Quantum Computations - Urmila Mahadev
1:47:31
Introduction to Query-to-Communication Lifting - Mika Goos
1:51:41
The GM-MDS conjecture - Shachar Lovett
1:05:07
Sunflowers and friends - Shachar Lovett
On the NP-hardness of 2-to-2 Games - Dor Minzer
59:14
X-Ramanujan graphs: ex uno plures - Ryan O'Donnell
1:08:35
2-universality of random graphs - Gal Kronenberg
2:00:55
Small-Set Expansion on the Grassmann Graph - Dor Minzer
1:13:55
Approximating the edit distance to within a constant factor in truly subquadratic time - Mike Saks
1:57:57
Asymptotic spectra and their applications II - Jeroen Zuiddam
1:10:40
Breaking the Circuit-Size Barrier in Secret Sharing - Vinod Vaikuntanathan
1:58:48
Tensor rank - Avi Wigderson
1:50:47
Asymptotic spectra and their applications I - Jeroen Zuiddam
1:09:34
Oracle Separation of Quantum Polynomial time and the Polynomial Hierarchy - Avishay Tal
1:02:59
Four and a half proofs of a product-measure version of the Erdös-Ko-Rado Theorem - Ehud Friedgut
1:50:45
A simple proof of a reverse Minkowski inequality - Noah Stephens-Davidowitz
1:16:13
Sums of Squares Over k-Subset Hypercubes - Annie Raymond
1:52:40
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet - Gil Cohen
LIVE
[Private video]
Circuit Lower Bounds for Nondeterministic Quasi-Polytime... - Cody Murray
1:41:00
Operator Scaling via Geodesically Convex Optimization, Invariant... (Continued) - Yuanzhi Li
1:20:03
Operator Scaling via Geodesically Convex Optimization, Invariant Theory... - Yuanzhi Li
1:44:27
Abstract Convexity, Weak Epsilon-Nets, and Radon Number - Shay Moran
1:50:05
Boolean function analysis: beyond the Boolean cube (continued) - Yuval Filmus
1:02:39
Boolean function analysis: beyond the Boolean cube - Yuval Filums
1:55:17
On the Communication Complexity of Classification Problems - Roi Livni
1:16:17
A Tight Bound for Hypergraph Regularity - Guy Moshkovitz
1:22:23
Some closure results for polynomial factorization - Mrinal Kumar
1:14:13
Nonlinear dimensionality reduction for faster kernel methods in machine learning - Christopher Musco
1:55:39
Outlier-Robust Estimation via Sum-of-Squares - Pravesh Kothari
1:21:10
Locally Repairable Codes, Storage Capacity and Index Coding - Arya Mazumdar
1:32:51
Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound II - Amnon Ta-Shma
1:21:08
Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound - Amnon Ta-Shma
1:45:49
A Constant-factor Approximation Algorithm for the Asymmetric Traveling Sale...- Ola Svensson
54:34
The Matching Problem in General Graphs is in Quasi-NC - Ola Svensson
1:57:27
A PSPACE construction of a hitting set for the closure of small algebraic circuits - Amir Shpilka
1:14:47
Recent advances in high dimensional robust statistics - Daniel Kane
1:32:16
Short proofs are hard to find (joint work w/ Toni Pitassi and Hao Wei) - Ian Mertz
1:09:18
General strong polarization - Madhu Sudan
2:03:23
Geometric complexity theory from a combinatorial viewpoint - Greta Panova
1:13:43
Locally testable and locally correctable codes approaching the GV bound - Shubhangi Saraf
2:03:20
A practical guide to deep learning - Richard Zemel
1:47:28
Learning models: connections between boosting...and regularity II - Russell Impagliazzo
1:12:00
Learning models: connections between boosting...and regularity I - Russell Impagliazzo
2:07:30
Pseudorandom generators for unordered branching programs - Eshan Chattopadhyay
1:14:40
Language edit distance, (min,+)(min,+)-matrix multiplication & beyond - Barna Saha
1:55:14
Cap-sets in (Fq)n(Fq)n and related problems - Zeev Dvir
1:04:04
Fooling intersections of low-weight halfspaces - Rocco Servedio
1:53:55
On the strength of comparison queries - Shay Moran
1:11:37
A nearly optimal lower bound on the approximate degree of AC00- Mark Bun
Structural aspects of the null-cone problem in invariant theory - Ankit Garg
1:07:48
Barriers for rank methods in arithmetic complexity - Rafael Oliveira
1:14:58
Crossing the logarithmic barrier for dynamic boolean data structure lower bounds - Omri Weinstein
1:52:07
Lifting theorems in communication complexity and applications - Toniann Pitassi
1:15:16
Rigorous RG: a provably efficient and possibly practical algorithm for... - Umesh Vazirani
1:00:34
The Complexity of the Non-commutative Determinant - Srikanth Srinivasan
1:31:58
Small-Bias Sets - Amir Yehudayoff
1:45:10
Existence of Small Families of t-wise Independent Permutations... - Shachar Lovett
1:06:22
Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Progress - Michael Forbes
2:02:10
Sparsity Lower Bounds for Dimensionality Reducing Maps - Jelani Nelson
1:58:01
Small set expander flows - Ali Kemal Sinop
1:48:09
Toward Better Formula Lower Bounds: An Information Complexity Approach... - Or Meir
1:08:46
A solution to Weaver's KS2KS2 - Adam Marcus
1:02:57
Polynomial Bounds for the Grid-Minor Theorem - Julia Chuzhoy
1:18:04
True Randomness: Its Origin and Expansion - Yaoyun Shi
1:49:54
Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression - Timothy Riley
56:24
Strong contraction and influences in tail spaces - Elchanan Mossel
1:08:43
Chernoff bounds for expander walks - Christopher Beck
1:29:42
Computing a categorical Gromov-Witten invariant - Andrei Căldăraru
2:01:08
Bounds on roots of polynomials (and applications) - Adam Marcus
1:06:07
Efficient empirical revenue maximization in single... - Yannai Gonczarowski
Mirror symmetry for moduli of flat bundles and non-abelian Hodge theory - Tony Pantev
1:30:51
Noncommutative probability for computer scientists - Adam Marcus
1:11:31
In pursuit of obfuscation - Allison Bishop
1:16:52
A time-space lower bound for a large class of learning problems - Ran Raz
1:05:26
Applications of monotone constraint satisfaction - Robert Robere
1:10:34
Approximate counting and the Lovasz local lemma - Ankur Moitra
2:04:05
Indistinguishability obfuscation from...to jumping pigs - Nir Bitansky
1:03:50
On the cryptographic hardness of finding a Nash equilibrium - Nir Bitansky
59:09
Interactive coding with...communication blowup - Yael Kalai
1:54:59
Structural and computational aspects of Brascamp-Lieb inequalities - Avi Wigderson
1:05:50
New insights on the (non)-hardness of circuit minimization and related problems - Eric Allender
1:48:13
A unified duality-based approach to Bayesian mechanism design - Matt Weinberg
1:53:49
52:40
Nearest neighbor search for general symmetric norms via embeddings... - Ilya Razenshteyn
1:03:48
Strongly Refuting Random CSPs below the spectral threshold - Prasad Raghavendra
1:19:53
Sketching and embedding are equivalent for norms - Alex Andoni
1:13:44
Quantifying tradeoffs between fairness and accuracy in online learning - Aaron Roth
1:57:19
Robust sensitivity - Shachar Lovett
1:01:07
Active learning with "simple" membership queries - Shachar Lovett
2:35:51
The polynomial method and the cap set problem - Jordan Ellenberg
2:02:51
Sum of squares lower bounds for refuting any CSP - Pravesh Kothari
1:03:22
On gradient complexity of measures on the discrete cube - Ronen Eldan
2:02:05
Approximate constraint satisfaction requires sub-exponential size linear programs - Pravesh Kothari
1:06:45
On the number of ordinary lines determined by sets in complex space - Shubhangi Saraf
1:39:21
Combinatorial rigidity of graphs embedded in R2 - Orit Raz
Stochastic block models and probabilistic reductions - Emmanuel Abbe
1:25:56
Theory of accelerated methods - Zeyuan Allen-Zhu
57:29
On the effect of randomness on planted 3-coloring models - Uri Feige
2:01:13
Non-malleable extractors for constant depth circuits, and affine functions - Eshan Chattopadhyay
2:05:38
Settling the complexity of computing approximate two-player Nash equilibria - Nash equilibria
2:18:46
Sum of squares, quantum entanglement, and log rank - David Steurer
1:00:12
On the query complexity of Boolean monotonicity testing - Xi Chen
1:45:45
Real rooted polynomials and multivariate extensions - Adam Marcus
53:23
Brains are better computers than computers - Eyal Wigderson
45:01
Happy Days - Gil Kalai joint with Einat Wigderson
1:46:25
Algebraic geometric codes and their applications - Gil Cohen
1:52:13
Fourier tails for Boolean functions and their applications - Avishay Tal
1:29:55
Reed-Muller codes for random erasures and errors - Amir Shpilka
1:57:28
A characterization of functions with vanishing averages over products of disjoint sets - Hatami
53:20
An average-case depth hierarchy theorem for Boolean - Li-Yang Tan
1:04:39
A local central limit theorem for triangles in a random graph - Swastik Kopparty
1:59:19
The Resolution proof system - Avi Wigderson
1:12:19
Polynomial-time tensor decompositions via sum-of-squares - Tengyu Ma
Proof complexity - an introduction - Avi Wigderson
1:58:34
Fast learning requires good memory - Ran Raz
1:08:25
Graph isomorphism in quasipolynomial time II - László Babai
1:29:57
Graph isomorphism in quasipolynomial time - László Babai
