Algorithms and Complexity Seminars
 |
Sharing is Hard: Paging problems for shared caches Wednesday, November 4, 2026 - 4:00pm to 5:00pm Memory hierarchies consist of fast and small caches in order to improve performance in the presence of the memory wall where access times to memory are substantially larger than the time it takes to compute. |
 |
Maximum Cardinality Matching in n^2 Time Wednesday, October 28, 2026 - 4:00pm to 5:00pm I will present a combinatorial n^2-time algorithm for the maximum matching problem, improving over the classical matrix multiplication based algorithms. |
 |
The Geometry of Fast Last-Iterate Learning in Games Thursday, October 29, 2026 - 4:00pm to 5:00pm Learning in games involves the study of online learning algorithms in strategic, multi-agent settings. |
 |
Eigenvalue bounds for Markov Chains on Multislices Thursday, October 22, 2026 - 4:00pm to 5:00pm Consider the following natural random walk whose states are the balanced vectors of $\{0,1\}^n$, i.e., the balanced Boolean slice with an equal number of $0$s and $1$s, where a single step of the random walk takes a state $u$ to a state $v$ at Hamming distance exactly |
 |
Decision Making under Imperfect Recall: Algorithms, Computational Complexity, and Benchmarks Thursday, October 15, 2026 - 4:00pm In this talk, we investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. |
 |
Local Node Differential Privacy Wednesday, October 14, 2026 - 4:00pm to 5:00pm How can we analyze sensitive graph data without trusting a central server? |
 |
Learning Confidence Sets Wednesday, October 7, 2026 - 4:00pm to 5:00pm I will discuss the problem of finding confidence sets for arbitrary distributions. This is a fundamental statistical task with connections to many problems, like support estimation, robust estimation, and conformal prediction. |
 |
Lower Bounds for Linear Hashing via Arithmetic Kakeya Wednesday, September 30, 2026 - 4:00pm to 5:00pm Affine modular linear hashing is one of the simplest classical hash families. For a prime p > u, the hash function is obtained by choosing s, t uniformly from Z_p and mapping each key x ∈ {0, ..., u - 1} to one of n bins by |
 |
This Week in Dynamic Optimality Wednesday, September 23, 2026 - 4:00pm to 5:00pm Sleator and Tarjan's dynamic optimality conjecture has been open since the mid 1980s. The premier data structures thought to be dynamically optimal are the Splay Tree and the Greedy BST. |
 |
What’s new in hash tables? Wednesday, September 16, 2026 - 4:00pm to 5:00pm The hash table was the very first (and second) data structure invented. So you would think we’d know pretty much all there is to know about them. Yet the last few years have seen the resolution of some surprisingly basic questions. |
 |
Hash Tables Like Onions Wednesday, September 9, 2026 - 4:00pm to 5:00pm Greedy open addressing is an extremely popular template for building hash tables, but it suffers from a fundamental drawback: performance degrades as the table fills up. |
 |
Static Retrieval Revisited: To Optimality and Beyond Wednesday, May 6, 2026 - 4:00pm to 5:00pm In this talk, we settle a classic open question in space-efficient data structures: the number of bits required to encode a key-value retrieval function that supports efficient queries. |
 |
Adversarial Robustness on Insertion-Deletion Streams Wednesday, April 29, 2026 - 4:00pm to 5:00pm We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. |
 |
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. |
 |
A mechanistic theory of hierarchical planning in the brain Wednesday, February 11, 2026 - 4:00pm to 5:00pm Goal-directed behavior in navigation and abstract tasks relies on hierarchical planning: long sequences are organized into subgoals and temporally extended actions. |
 |
Agreement testers and PCPs from coset complexes Wednesday, February 4, 2026 - 4:00pm to 5:00pm "Agreement testers” are objects used in the design of (some) probabilistically checkable proofs, which, in turn, play a fundamental role in modern complexity theory and cryptography. |
 |
Free Probability and Its Applications to TCS Wednesday, January 28, 2026 - 4:00pm to 5:00pm What does it mean for two matrices to be independent, while preserving properties that make “independence” useful? More generally, how should one define independence for random variables in noncommutative settings? |
 |
Low-Query Locally Testable Codes Wednesday, November 12, 2025 - 4:00pm to 5:00pm Locally testable codes (LTCs) are a special kind of error correcting codes where the receiver can correctly detect, with high probability, whether the received data was significantly corrected by reading just a few of its letters (chosen at random according to some distr |
 |
Fast Mixing of 1D Quantum Gibbs Samplers at All Temperatures Monday, October 27, 2025 - 3:00pm to 4:00pm Recently, quantum computing analogs of classical Gibbs samplers have been introduced—quantum Markov chains that generalize Glauber or Metropolis dynamics, and serve as models of nature’s thermalization process. |
 |
Fault-Tolerance in Buy-at-Bulk and Hop-Constrained Network Design Wednesday, October 22, 2025 - 4:00pm to 5:00pm Buy-at-bulk network design is a classical and practically motivated problem, in which the goal is to construct a low-cost network that supports multi-commodity flow between given node pairs. |
 |
Which Algorithms Have Tight Generalization Bounds? Wednesday, December 10, 2025 - 3:00pm to 4:00pm Ge |
Pages
