Algorithms and Complexity Seminars
 |
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
