Theory Seminars

Zihan Tan: TBD

Or Zamir: Algorithmic Applications of Hypergraph and Partition Containers

Sasha Golovnev: Polynomial formulations as a barrier for reduction-based hardness proofs

Min Jae Song: Continuous LWE

Manik Dhar: ℓ∞ linear hashing and two-sided Kakeya bounds

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