Tight Thresholds for Cuckoo Hashing via XORSAT
From MaRDI portal
Publication:3587381
DOI10.1007/978-3-642-14165-2_19zbMath1256.68047OpenAlexW1528625750MaRDI QIDQ3587381
Rasmus Pagh, Michael Rink, Martin Dietzfelbinger, Michael Mitzenmacher, Andrea Montanari, Andreas Goerdt
Publication date: 7 September 2010
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_19
Related Items
Sharp load thresholds for cuckoo hashing ⋮ Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables ⋮ Hardness of peeling with stashes ⋮ Satisfiability Thresholds beyond k −XORSAT ⋮ On the phase transition in random simplicial complexes ⋮ Online Stochastic Matching: Online Actions Based on Offline Statistics ⋮ Greedy Matching in Bipartite Random Graphs ⋮ Load Thresholds for Cuckoo Hashing with Overlapping Blocks ⋮ Maximum independent sets on random regular graphs ⋮ Matchings on infinite graphs ⋮ Load Thresholds for Cuckoo Hashing with Overlapping Blocks ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Cuckoo hashing in cryptography: optimal parameters, robustness and applications ⋮ Orientability Thresholds for Random Hypergraphs ⋮ The Satisfiability Threshold fork-XORSAT ⋮ The Multiple-Orientability Thresholds for Random Hypergraphs ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ Self-stabilizing repeated balls-into-bins ⋮ Thresholds for extreme orientability ⋮ Dynamic space efficient hashing ⋮ The satisfiability threshold for random linear equations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The set of solutions of random XORSAT formulae ⋮ Core forging and local limit theorems for the \(k\)-core of random graphs ⋮ The solution space geometry of random linear equations ⋮ A new approach to the orientation of random hypergraphs ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Fast scalable construction of ([compressed static | minimal perfect hash) functions] ⋮ Dynamic Space Efficient Hashing. ⋮ Belief propagation on the random \(k\)-SAT model ⋮ Phase transition of the 3-majority dynamics with uniform communication noise ⋮ Unnamed Item ⋮ The rank of sparse random matrices ⋮ Towards optimal degree distributions for left-perfect matchings in random bipartite graphs
