Algorithms and Complexity Seminars
 |
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 - 4:00pm to 5: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. |
 |
TBA Wednesday, December 3, 2025 - 4:00pm to 5:00pm TBA |
 |
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? |
 |
Zeroth-order log-concave sampling: Uniform sampling from convex bodies Wednesday, November 5, 2025 - 4:00pm to 5:00pm Since the development of the first randomized polynomial-time algorithm for volume computation by Dyer, Frieze, and Kannan in 1989, convex-body sampling has been a central problem at the intersection of algorithms, geometry, and probability. |
 |
The Mysterious Query Complexity of Tarski Fixed Points Wednesday, October 29, 2025 - 4:00pm to 5:00pm |
 |
Quality Control on Random Graphs in Sublinear Time Wednesday, October 15, 2025 - 4:00pm to 5:00pm Many algorithms are designed to perform well on random instances. However, when running such an algorithm on a specific input, can we trust its output? |
 |
Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair Wednesday, October 8, 2025 - 4:00pm to 5:00pm We give a reduction from $(1+\epsilon)$-approximate Earth Mover's Distance (EMD) to $(1+\epsilon)$-approximate Closest Pair. As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. |
Pages
