Pseudo-random graphs and bit probe schemes with one-sided error

DOI10.1007/s00224-012-9425-0zbMath1319.68066arXiv1102.5538OpenAlexW1999495042MaRDI QIDQ2254500

Andrei Romashchenko

Publication date: 5 February 2015

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.5538

zbMATH Keywords

data structuresderandomizationpseudorandom number generatorsexpander graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ On extracting space-bounded Kolmogorov complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Cuckoo hashing: Further analysis
• Families of finite sets in which no set is covered by the union of \(r\) others
• Pseudorandom generators for space-bounded computation
• On the complexity of an optimal non-blocking commutation scheme without reorganization
• Hardness vs randomness
• Storing information with extractors.
• How strong is Nisan's pseudo-random generator?
• Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
• Construction of extractors using pseudo-random generators (extended abstract)
• Are Bitvectors Optimal?
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Expander graphs and their applications
• Algorithmic derandomization via complexity theory
• Randomness conductors and constant-degree lossless expanders
• De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Membership in Constant Time and Almost-Minimum Space
• Nonoblivious hashing
• Eigenvalues and expansion of regular graphs
• Cuckoo hashing
• Loss-less condensers, unbalanced expanders, and extractors
• On the cell probe complexity of membership and perfect hashing
• Space/time trade-offs in hash coding with allowable errors
• Extracting all the randomness and reducing the error in Trevisan's extractors

This page was built for publication: Pseudo-random graphs and bit probe schemes with one-sided error