Theory Seminars

Zihan Tan: TBD

Sophie Huiberts: Smoothed analysis of the simplex method

Liren Shan: Higher-Order Cheeger Inequality for Partitioning with Buffers

William Hoza: Recent Progress on Derandomizing Space-Bounded Computation

Jessica Sorrell: Replicability in Learning

Yang Liu: Lessons on Algorithmic Graph Theory from Maxflow

Aaron Bernstein: Negative-Weight Single-Source Shortest Paths in Near-linear Time

Sorrachai Yingchareonthawornchai: Deterministic Small Vertex Connectivity in Almost Linear Time

Vincent Cohen-Addad: Sublinear time algorithms for Euclidean clustering coresets and correlation clustering

Haotian Jiang: Resolving Matrix Spencer Conjecture Up to Polylogarithmic Rank

Zeyu Guo: Fast Multivariate Multipoint Evaluation over All Finite Fields

Fernando Granha Jeronimo: Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

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