Algorithms and Complexity Seminars
 |
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? |
 |
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. |
 |
Faster Mixing of the Jerrum-Sinclair Chain Wednesday, October 1, 2025 - 4:00pm to 5:00pm We show that the Jerrum-Sinclair Markov chain on matchings mixes in time $\widetilde{O}(\Delta^2 m)$ on any graph with $n$ vertices, $m$ edges, and maximum degree $\Delta$, for any constant edge weight $\lambda>0$. |
 |
Learning and Incentives in Human–AI Collaboration Wednesday, September 24, 2025 - 4:00pm to 5:00pm As AI systems become more capable, a central challenge is designing them to work effectively with humans. |
Pages
