The condensation transition in random hypergraph 2-coloring
From MaRDI portal
Publication:5743395
zbMath1421.68068arXiv1107.2341MaRDI QIDQ5743395
Amin Coja-Oghlan, Lenka Zdeborová
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1107.2341
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Average-case complexity without the black swans ⋮ Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ The Number of Satisfying Assignments of Random Regulark-SAT Formulas ⋮ A topological dynamical system with two different positive sofic entropies ⋮ On the number of solutions in random hypergraph 2-colouring ⋮ Statistical limits of spiked tensor models ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ Panchromatic 3-colorings of random hypergraphs ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ On the structure of the set of panchromatic colorings of a random hypergraph ⋮ The asymptotic \(k\)-SAT threshold ⋮ Bounds on threshold probabilities for coloring properties of random hypergraphs ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ On panchromatic colourings of a random hypergraph ⋮ Two-Colorings of a Random Hypergraph ⋮ Random hypergraphs and property B ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Circular coloring of random graphs: statistical physics investigation ⋮ Panchromatic colorings of random hypergraphs ⋮ Spin systems on Bethe lattices ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ The condensation phase transition in random graph coloring ⋮ Colorings of partial Steiner systems and their applications ⋮ Phase Transitions in Discrete Structures ⋮ The number of solutions for random regular NAE-SAT ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Biased landscapes for random constraint satisfaction problems ⋮ On the chromatic number of a random hypergraph
Cites Work
- Unnamed Item
- Unnamed Item
- Random subcubes as a toy model for constraint satisfaction problems
- Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
- Component structure in the evolution of random hypergraphs
- The 3-XORSAT threshold.
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- Pairs of SAT-assignments in random Boolean formulæ
- Reconstruction and Clustering in Random Constraint Satisfaction Problems
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Sharp thresholds of graph properties, and the $k$-sat problem
- Two‐coloring random hypergraphs
- Hunting for sharp thresholds
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- On the solution-space geometry of random constraint satisfaction problems
- On the solution‐space geometry of random constraint satisfaction problems
- The two possible values of the chromatic number of a random graph