Theory Seminars

Optimal Memory Allocation: The Dos and Don’ts of Request Fragmentation

An Almost Logarithmic Approximation for Cutwidth

On the Existence of Seedless Condensers: Exploring the Terrain

Exact Emulators for Planar Graphs

Recent progresses on Correlation Clustering

New techniques for convex optimization and sparsification

New Approximation Bounds for Small-Set Vertex Expansion

Gaussian Polytope Approximators

Separating MAX 2-AND, MAX DI-CUT and MAX CUT

Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation

Are there graphs whose shortest path structure requires large edge weights?

Deeparnab Chakrabarty: Parallel Submodular Function Minimization

Victor Reis: Optimal Online Discrepancy Minimization

Lars Rohwedder: Simpler and stronger approximation algorithms for flow time scheduling

Zihan Tan: Almost-Optimal Sublinear Additive Spanners

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