Theory of Computation Seminars

Coin Toss: Game-Theoretic Fairness and Privacy.

Turán-type Problems and Graph Sparsification

Rate vs. Distance – Milestones and Obstacles Towards Improved Bounds

Testing Assumptions of Learning Algorithms

Maximum Matching in $O(\log \log n) $ Passes in Dynamic Streams

Worst-Case Approximation Ratios for Some Constraint Satisfaction Problems

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