Algorithms and Complexity Seminars

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.

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.

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?

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$.

Can memory be useful even when it's already full? In the catalytic computing model (Buhrman et al.

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.

Score estimation is the backbone of score-based generative models (SGMs), especially denoising diffusion probabilistic models (DDPMs).