Theory Seminars

Haotian Jiang: Minimizing Convex Functions with Integral/Rational Minimizers

Mitali Bafna: Playing Unique Games on Certifiable Small-Set Expanders and High-Dimensional Expanders

Parth Mittal: Brooks’ Theorem in Graph Streams

Huacheng Yu: TBD

Max Hopkins: Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments

Ryan Williams: Constructive Separations and Their Consequences

Santhoshini Velusamy: Approximating CSPs in the streaming setting

Robert Robere: Pseudorandom Self-Reductions for NP-Complete Problems

Deeksha Adil: Fast Algorithms for l_p-Regression and Other Problems

Michael Dinitz: Faster Matchings via Learned Duals

Ce Jin: Fast Low-Space Algorithms for Subset Sum

Arun Jambulapati: Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

Vera Traub: Better-Than-2 Approximations for Weighted Tree Augmentation

A Characterization of Approximability for Biased CSPs

APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time

Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering

Arnold Filtser: Clan Embeddings into Trees, and Low Treewidth Graphs

Optimization-friendly generic mechanisms without money.

Breaking the 2^n barrier for 5-coloring and 6-coloring

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

On the Complexity of Consensus-Halving and Necklace Splitting

Accelerating Sampling Algorithms via Domain Sparsification

The Complexity of Gradient Descent: CLS = PPAD∩PLS

k-Forrelation Optimally Separates Quantum and Classical Query Complexity

Negative probabilities: what are they for?