Almost random graphs with simple hash functions

DOI10.1145/780542.780634zbMath1192.68227OpenAlexW2059271645MaRDI QIDQ3581260

Martin Dietzfelbinger, Philipp Woelfel

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780634

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Information storage and retrieval of data (68P20) Randomized algorithms (68W20)

Related Items (10)

Efficient set intersection with simulation-based security ⋮ Balanced allocation and dictionaries with tightly packed constant size bins ⋮ Bloom Filters in Adversarial Environments ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ Hardness-preserving reductions via cuckoo hashing ⋮ An improved version of cuckoo hashing: average case analysis of construction cost and search operations ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ Bet-or-pass: adversarially robust Bloom filters ⋮ Explicit and efficient hash families suffice for cuckoo hashing with a stash

This page was built for publication: Almost random graphs with simple hash functions