Theory Seminars

Hypergraph k-cut for fixed k in deterministic polynomial time

Non-Adaptive Adaptive Sampling in Turnstile Streams

The Menu-Size of Approximately Optimal Auctions

An Algorithm for Hypergraph k-Cut

Towards a Unified Theory of Matching Sparsifiers

Security Games: Quasi-Regular Sequences, and a new version of TSP

The Complexity of Finding S-factors in Regular Graphs

Fine-grained hardness of CVP(P)— Everything that we can prove (and nothing else)

An Adaptive Step Toward the Multiphase Conjecture

Cup Emptying Games and I/O Scheduling

Parallelizing Greedy for Submodular Set Function Maximization

The polymorphic gateway between structure and algorithms: Constraint Satisfaction and Beyond

Expander Decompositions: Fast Algorithms and Applications

Revisionist Simulations: A New Technique for Proving Space Lower Bounds

On the Quantitative Hardness of the Closest Vector Problem

Constant Time Coloring in the Congested Clique

Efficient Density Evaluation for Smooth Kernels

Dynamic Spanning Forest: Techniques and Connections to Other Fields

Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

The Unreasonable Effectiveness of Almost Optimal Hardness

Nearly complete graphs decomposable into large induced matchings and their applications

Why Extension-based Proofs Fail

The Power of Natural Properties as Oracles

The Structure of Unique Shortest Paths in Graphs

Recent Progress in Bipartite Matching Problems

Linear Sketching for Functions over the Boolean Hypercube