Algorithms and Complexity Seminars

Spectral Clustering in Birthday Paradox Time
Wednesday, April 22, 2026 - 4:00pm to 5:00pm
Given a vertex in a (k,φ,ϵ)-clusterable graph, i.e., a graph whose vertex set can be partitioned into a disjoint union of φ-expanders of size ≈n/k with outer conductance bounded by ϵ, can one quickly tell which cluster it belongs to?
Efficient Learning Algorithms under (Heavy) Contamination
Thursday, April 16, 2026 - 4:00pm to 5:00pm
In this talk, I will present a series of new results in supervised learning from contaminated datasets, based on a general outlier removal algorithm inspired by recent work on learning with distribution shift.
 
Randomized Greedy Matching on General Graphs
Wednesday, April 15, 2026 - 4:00pm to 5:00pm
Randomized greedy algorithms are among the simplest and most effective methods for approximating maximum matchings, yet their performance on general graphs remains much less well understood than in the bipartite setting.
On the stability of shortest path algorithms
Thursday, April 9, 2026 - 3:00pm to 4:00pm

Optimization problems on random instances frequently appear in statistics and theoretical computer science, and many of them appear to be hard to solve with efficient algorithms.

Stable Open Addressing and the Curse of Reappearance Dependencies
Wednesday, April 8, 2026 - 4:00pm to 5:00pm
Stable hash tables—hash tables that never move existing elements—are among the simplest and most widely used hashing schemes. Two canonical examples are stable uniform probing and stable linear probing.
Half-Approximating Maximum Dicut in the Streaming Setting
Wednesday, March 18, 2026 - 4:00pm to 5:00pm
This talk is based on joint work with Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian, to appear at STOC'26. We study streaming algorithms for the maximum directed cut problem.
Lower Bounds for Non-adaptive Local Computation Algorithms
Wednesday, March 11, 2026 - 4:00pm to 5:00pm

We study non-adaptive

Ideals, Macaulay Bases, and PCPs
Wednesday, March 4, 2026 - 4:00pm to 5:00pm
The PCP Theorem is a central result in theoretical computer science, giving query-efficient verifiers for NP.
Upper and Lower Bounds for the Linear Ordering Principle
Wednesday, February 25, 2026 - 4:00pm to 5:00pm

The Linear Ordering Principle (LOP) is a total search problem that generalizes the task of finding the minimum element of a given order to settings in which the order need not be total.

Memory Reallocation with Polylogarithmic Overhead
Wednesday, February 18, 2026 - 4:00pm to 5:00pm

The \emph{Memory Reallocation problem} asks to dynamically maintain an assignment of given objects of various sizes to non-overlapping contiguous chunks of memory, while supporting updates (insertions/deletions) in an online fashion.

Pages

Subscribe to Algorithms and Complexity Seminars