Algorithms and Complexity Seminars
 |
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 |
 |
Fast Algorithms for Graph Arboricity and Related Problems Wednesday, November 19, 2025 - 4:00pm to 5:00pm We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in \sqrt{n} m^{1+o(1)} time. |
 |
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams Wednesday, December 3, 2025 - 4:00pm to 5:00pm In the dynamic streaming model, an $n$-vertex input graph is defined through a sequence of edge insertions and deletions in a stream. The algorithms are allowed to process this stream in multiple passes while using O(n \poly\log{(n)}) space. |
 |
Memory as a lens to understand learning and optimization Monday, October 20, 2025 - 4:00pm to 5:00pm What is the role of memory in learning and optimization? |
Pages
