Archive for April, 2010

ICALP papers

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.