Theory Seminars

Arun Jambulapati: Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

Michael Dinitz: TBD

Deeksha Adil

Huacheng Yu: TBD

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?

The zero-rate threshold of adversarial bit-deletions is less than 1/2

Reversing Color Coding

Information theoretic limits of cardinality estimation: Fisher meets Shannon

Approximation Algorithms for Fair Clustering

Adaptive gradient descent methods for constrained optimization

An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature

(a biased selection of) Recent Developments in Combinatorial Auctions

Approximation Algorithms and Hardness for Strong Unique Games

Adversarial Streaming, Differential Privacy, and Adaptive Data Analysis

Prophet and Secretary Online Algorithms for Matching in General Graphs

Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

Deterministic Mincut in Almost-Linear Time