From Independence to Expansion and Back Again

Tobias Lybecker Christiani, Rasmus Pagh, Mikkel Thorup

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstrakt

We consider the following fundamental problems: (1) Constructing k-independent hash functions with a space-time tradeoff close to Siegel's lower bound. (2) 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.
OriginalsprogEngelsk
TitelSTOC '15 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing
ForlagACM New York, NY, USA
Publikationsdato2015
Sider813-820
ISBN (Trykt)978-1-4503-3536-2
DOI
StatusUdgivet - 2015

Emneord

  • hashing
  • k-independence
  • expanders

Fingeraftryk

Dyk ned i forskningsemnerne om 'From Independence to Expansion and Back Again'. Sammen danner de et unikt fingeraftryk.

Citationsformater