Theory Seminars

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

Theory Seminar Kick-off

Distributed Edge Coloring

Near-optimal linear decision trees for k-SUM and related problems

Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts

Eliciting Expert Information without Verification

Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

Property testing in the presence of erased data