From independence to expansion and back again

Tobias Lybecker Christiani; Rasmus Pagh; Mikkel Thorup

doi:10.1145/2746539.2746620

From independence to expansion and back again

Tobias Lybecker Christiani, Rasmus Pagh, Mikkel Thorup

Department of Computer Science

8 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing : STOC '15
Number of pages	8
Publisher	Association for Computing Machinery
Publication date	14 Jun 2015
Pages	813-820
ISBN (Print)	978-1-4503-3536-2
DOIs	https://doi.org/10.1145/2746539.2746620
Publication status	Published - 14 Jun 2015
Event	Annual ACM Symposium on the Theory of Computing 2015 - Portland, United States Duration: 15 Jun 2015 → 17 Jun 2015 Conference number: 47

Conference

Conference	Annual ACM Symposium on the Theory of Computing 2015
Number	47
Country/Territory	United States
City	Portland
Period	15/06/2015 → 17/06/2015

Access to Document

10.1145/2746539.2746620

http://doi.acm.org/10.1145/2746539.2746620

Cite this

From independence to expansion and back again. / Christiani, Tobias Lybecker; Pagh, Rasmus; Thorup, Mikkel.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing: STOC '15. Association for Computing Machinery, 2015. p. 813-820.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

@inproceedings{021ed856fc3d49a9bda5b1bbe0196bcd,

title = "From independence to expansion and back again",

abstract = "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.",

keywords = "bipartite expanders, hash functions, k-independence",

author = "Christiani, {Tobias Lybecker} and Rasmus Pagh and Mikkel Thorup",

year = "2015",

month = jun,

day = "14",

doi = "10.1145/2746539.2746620",

language = "English",

isbn = "978-1-4503-3536-2",

pages = "813--820",

booktitle = "Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

note = "Annual ACM Symposium on the Theory of Computing 2015, STOC '15 ; Conference date: 15-06-2015 Through 17-06-2015",

}

TY - GEN

T1 - From independence to expansion and back again

AU - Christiani, Tobias Lybecker

AU - Pagh, Rasmus

AU - Thorup, Mikkel

N1 - Conference code: 47

PY - 2015/6/14

Y1 - 2015/6/14

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

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

KW - bipartite expanders, hash functions, k-independence

U2 - 10.1145/2746539.2746620

DO - 10.1145/2746539.2746620

M3 - Article in proceedings

SN - 978-1-4503-3536-2

SP - 813

EP - 820

BT - Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - Annual ACM Symposium on the Theory of Computing 2015

Y2 - 15 June 2015 through 17 June 2015

ER -

From independence to expansion and back again

Abstract

Conference

Access to Document

Fingerprint

Cite this