Theory Seminars

New Analysis of the Factor Refinement Algorithm with Applications

Fast algorithms for linear programs and bipartite matching via new data structures and interior-point methods

Impartial selection, additive approximation guarantees, and priors

A Unified and Fine-Grained Approach for Light Spanners

Edge-Weighted Online Bipartite Matching

Coloring and Maximum Weight Independent Set of Rectangles

Towards Optimal Separations between Quantum and Randomized Query Complexities

Computational Hardness of Optimal Fair Computation

Aggregating Inconsistent Information in Ranking, Clustering and Phylogenetic Trees

New Techniques for Proving Fine-Grained Average-Case Hardness

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