No less than 3 papers at ICALP 2010 have co-authors from our group:

**Tight Thresholds for Cuckoo Hashing via XORSAT** settles a question that has been open since 2003, on the space usage of cuckoo hashing using d>2 hash functions. The approach is to show a tight connection to prior work on random instances of the XORSAT problem (defined by a system of linear equations). We further generalize this to a setting where the number of hash functions is a random variable (and d denotes its mean).

**Covering and Packing in Linear Space** continues an investigation of the fast zeta transform, a powerful algorithm from the 1930s that is in many aspects similar to the fast Fourier transform. We’ve used the FZT a lot in a number of recent papers to speed up several problems, but the speed-up always comes at the expense of space. So here we show how to perform FZT in small (and in some sense, optimal) space.

**Exponential Time Complexity of the Permanent and the Tutte Polynomial** shows that two algorithms for important counting problems are optimal: Ryser’s 1962 formula for computing the permanent, and our own algorithm from 2008 for the Tutte polynomial: both of these problems require time exp(Ω(*n*)), where *n* is the matrix dimension, or number of vertices, respectively. The optimality is established under the exponential time hypothesis (ETH); in fact, the paper also contains a conceptual contribution in that we define the corresponding counting hypothesis, #ETH.

## Recent Comments