A Probabilistic Study on Combinatorial Expanders and Hashing

DOI10.1137/S009753970444630XMaRDI QIDQ5454244zbMATH OpenDBLPWikidataFDO

Authors Phillip G. Bradford, Michael N. Katehakis

Publication date 28 March 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S009753970444630X

zbMATH Keywords

combinatorial expandersdouble hashingexpander graphsexpansion factorGabber-Galil expanderhash collisionspairwise independence

Mathematics Subject Classification ID

Applications of graph theory (05C90) Combinatorial probability (60C05) Data structures (68P05) Information storage and retrieval of data (68P20)

Recommendations

• The analysis of double hashing
• Limitations on Explicit Constructions of Expanding Graphs
• Cryptographic hash functions from expander graphs
• From independence to expansion and back again
• Cryptographic hash functions from sequences of lifted Paley graphs

Cited in

(1)

• On probabilistic analysis of a coalesced hashing algorithm

This page was built for publication: A Probabilistic Study on Combinatorial Expanders and Hashing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5454244)