From Independence to Expansion and Back Again
- Tobias Lybecker Christiani,
- Rasmus Pagh,
- Mikkel Thorup
- ,
- ,
- University of Copenhagen
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-review
Open access
Publication Information
Output type
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 813-820Publication milestones
- Published - 2015
Publication status
Published - 2015
Publisher
Association for Computing Machinery, United StatesISBN (Print)
978-1-4503-3536-2Publication IDs
- Scopus: 84945589219
Host publication title
STOC '15 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of ComputingAbstract
We consider the following fundamental problems:
• Constructing k-independent hash functions with a spacetime
tradeoff close to Siegel’s lower bound.
• Constructing representations of unbalanced expander graphs having small size and allowing fast computation of the neighbor function.
It is not hard to show that these problems are intimately connected in the sense that a good solution to one of them leads to a good solution to the other one. In this paper we exploit
this connection to present efficient, recursive constructions of k-independent hash functions (and hence expanders with a small representation). While the previously most efficient construction (Thorup, FOCS 2013) needed time quasipolynomial in Siegel’s lower bound, our time bound is just a logarithmic factor from the lower bound.
• Constructing k-independent hash functions with a spacetime
tradeoff close to Siegel’s lower bound.
• Constructing representations of unbalanced expander graphs having small size and allowing fast computation of the neighbor function.
It is not hard to show that these problems are intimately connected in the sense that a good solution to one of them leads to a good solution to the other one. In this paper we exploit
this connection to present efficient, recursive constructions of k-independent hash functions (and hence expanders with a small representation). While the previously most efficient construction (Thorup, FOCS 2013) needed time quasipolynomial in Siegel’s lower bound, our time bound is just a logarithmic factor from the lower bound.
Publication metrics
PlumX, opens in new tab
Captures
22
Citations
15