The k-orientability thresholds for Gn, p

No abstract is available for this paper.

• Publication year

  2007

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2007-01-07

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation

  2007cited by this paper
• A simple solution to the k‐core problem

  2005cited by this paper
• Balanced allocation and dictionaries with tightly packed constant size bins

  2005influential reference
• Efficient hashing with lookups in two memory accesses

  2004influential reference
• Cores and Connectivity in Sparse Random Graphs

  2004cited by this paper
• The pure literal rule threshold and cores in random hypergraphs

  2004cited by this paper
• Directed graphs, Hamiltonicity and doubly stochastic matrices

  2004cited by this paper
• The Poisson Cloning Model for Random Graphs, Random Directed Graphs and Random k-SAT Problems

  2004cited by this paper
• Two-way hashing with separate chaining and linear probing

  2004influential reference
• Space Efficient Hash Tables with Worst Case Constant Access Time

  2003cited by this paper
• Cuckoo Hashing

  2001cited by this paper
• Balanced Allocations

  1999cited by this paper
• Random Graphs, Random Walks, Differential Equations and the Probabilistic Analysis of Algorithms

  1998cited by this paper
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence

  1998cited by this paper
• Randomized allocation processes

  1997influential reference
• Sudden Emergence of a Giantk-Core in a Random Graph

  1996cited by this paper
• A Critical Point for Random Graphs with a Given Degree Sequence

  1995cited by this paper
• Efficient PRAM simulation on a distributed memory machine

  1992influential reference
• Storing a sparse table with O(1) worst case access time

  1982influential reference
• A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs

  1980cited by this paper

• Smash: Flexible, Fast, and Resource-Efficient Placement and Lookup of Distributed Storage

  2025cites this paper
• Efficient $d$-ary Cuckoo Hashing at High Load Factors by Bubbling Up

  2025cites this paper
• Optimal Non-oblivious Open Addressing

  2025cites this paper
• O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold

  2024cites this paper
• Smash: Flexible, Fast, and Resource-efficient Placement and Lookup of Distributed Storage

  2023cites this paper
• EdgeCut: Fast and Low-Overhead Access of User-Associated Contents from Edge Servers

  2023influential citation
• Rigid partitions: From high connectivity to random graphs

  2023cites this paper
• What if we tried Less Power? - Lessons from studying the power of choices in hashing-based data structures

  2023influential citation
• Sharp threshold for rigidity of random graphs

  2022cites this paper
• Detection Threshold for Correlated Erdős-Rényi Graphs via Densest Subgraph

  2022cites this paper
• Matching recovery threshold for correlated random graphs

  2022cites this paper
• Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold

  2022cites this paper
• Ludo Hashing

  2020influential citation
• Random hypergraphs for hashing-based data structures

  2020cites this paper
• Peeling Close to the Orientability Threshold Spatial Coupling in Hashing-Based Data Structures

  2020cites this paper
• Dense Peelable Random Uniform Hypergraphs

  2019cites this paper
• PIR with Compressed Queries and Amortized Query Processing

  2018cites this paper
• A Ramsey property of random regular and k ‐out graphs

  2017cites this paper
• EMOMA: Exact Match in One Memory Access

  2017cites this paper
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks

  2017influential citation
• Hashing, Load Balancing and Multiple Choice

  2017cites this paper
• Balanced allocation through random walk

  2017cites this paper
• SPARSE RANDOM GRAPHS Structure & Dynamics

  2017cites this paper
• Hashing , Load Balancing and Multiple Choice DRAFT ∗

  2017cites this paper
• A Faster Algorithm for Cuckoo Insertion and Bipartite Matching in Large Graphs

  2016cites this paper
• Long Cycles in Locally Expanding Graphs, with Applications

  2016cites this paper
• Sandwiching a densest subgraph by consecutive cores

  2015influential citation
• 2-2012 Thresholds for Extreme Orientability

  2015cites this paper
• Thresholds for Matchings in Random Bipartite Graphs with Applications to Hashing-Based Data Structures

  2015cites this paper
• The stripping process can be slow: Part I

  2015cites this paper
• Multiple choice allocations with small maximum loads

  2014cites this paper
• Inside the clustering threshold for random linear equations

  2013cites this paper
• Load-balancing and resource-provisioning in large distributed systems. (Équilibrage de charge et répartition de ressources dans les grands systèmes distribués)

  2013cites this paper
• 0 O ct 2 01 3 On the Insertion Time of Cuckoo Hashing ∗

  2013cites this paper
• Arboricity and spanning‐tree packing in random graphs

  2013cites this paper
• Double hashing thresholds via local weak convergence

  2013cites this paper
• Balls into Bins Made Faster

  2013cites this paper
• The densest subgraph problem in sparse random graphs

  2013cites this paper
• Arboricity and spanning-tree packing in random graphs with an application to load balancing

  2013cites this paper
• Thresholds for Extreme Orientability

  2012cites this paper
• On Randomness in Hash Functions

  2012cites this paper
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing

  2012cites this paper
• A new approach to the orientation of random hypergraphs

  2012cites this paper
• A Cuckoo Hashing Variant with Improved Memory Utilization and Insertion Time

  2011cites this paper
• The multiple-orientability thresholds for random hypergraphs

  2011cites this paper
• Cuckoo Hashing with Pages

  2011cites this paper
• The rigidity transition in random graphs

  2010cites this paper
• Orientability of Random Hypergraphs and the Power of Multiple Choices

  2010cites this paper
• On the Insertion Time of Cuckoo Hashing

  2010cites this paper
• Generation and properties of random graphs and analysis of randomized algorithms

  2010cites this paper
• Load balancing and orientability thresholds for random hypergraphs

  2010cites this paper
• Orientability Thresholds for Random Hypergraphs

  2010influential citation
• Some Open Questions Related to Cuckoo Hashing

  2009cites this paper
• 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit

  2009cites this paper
• Ramsey games with giants

  2009influential citation
• Coloring the edges of a random graph without a monochromatic giant component

  2009cites this paper
• On risks of using a high performance hashing scheme with common universal classes

  2009cites this paper
• Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

  2009cites this paper
• Sharp load thresholds for cuckoo hashing

  2009cites this paper
• Tight Thresholds for Cuckoo Hashing via XORSAT

  2009influential citation
• Succinct Data Structures for Retrieval and Approximate Membership

  2008cites this paper
• The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation

  2007influential citation