Algorithms and Complexity Seminars
 |
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. |
 |
Distribution Learning with Advice Friday, September 19, 2025 - 2:00pm to 3:00pm We revisit the problem of distribution learning within the framework of learning-augmented algorithms. |
 |
Metric Embeddings with Outliers Wednesday, September 17, 2025 - 2:00pm to 3:00pm |
 |
Catalytic Computing: A Primer Wednesday, May 14, 2025 - 3:00pm to 4:00pm Can memory be useful even when it's already full? In the catalytic computing model (Buhrman et al. |
 |
Understanding the Trade-Offs Between Hallucinations and Mode Collapse in Language Generation Thursday, May 1, 2025 - 4:00pm to 5:00pm Specifying all desirable properties of a language model is challenging, but certain requirements seem essential. |
 |
How to Appease a Voter Majority Wednesday, April 30, 2025 - 4:00pm to 5:00pm In 1785, Condorcet established a frustrating property of elections and majority rule: it is possible that, no matter which candidate you pick as the winner, a majority of voters will prefer someone else. |
 |
Revisiting the Predictability of Social Events Wednesday, April 23, 2025 - 4:00pm to 5:00pm Social predictions do not passively describe the future; they actively shape it. They inform actions and change individual expectations in ways that influence the likelihood of the predicted outcome. Given these dynamics, to what extent can social events be predicted? |
 |
DDPM Score Matching and Distribution Learning Wednesday, April 16, 2025 - 4:00pm to 5:00pm Score estimation is the backbone of score-based generative models (SGMs), especially denoising diffusion probabilistic models (DDPMs). |
Pages
