Algorithms and Complexity Seminars

The hash table was the very first (and second) data structure invented.  So you would think we’d know pretty much all there is to know about them.  Yet the last few years have seen the resolution of some surprisingly basic questions.

We study non-adaptive

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.

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?

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.

Ge

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.