On the Circuit Complexity of Perfect Hashing

DOI10.1007/978-3-642-22670-0_4zbMath1343.94057OpenAlexW2295125609MaRDI QIDQ3088172

Avi Wigderson, Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_4

zbMATH Keywords

circuit complexityperfect hashing

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Cryptography (94A60)

Cites Work

• Unnamed Item
• New bounds for perfect hashing via information theory
• Universal classes of hash functions
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Perfect Hashing and Probability

This page was built for publication: On the Circuit Complexity of Perfect Hashing