The satisfiability threshold for random linear equations
From MaRDI portal
Publication:2003764
DOI10.1007/s00493-019-3897-3zbMath1463.05507arXiv1710.07497OpenAlexW3009270753MaRDI QIDQ2003764
Pu Gao, Amin Coja-Oghlan, Peter Ayre, Noela Müller
Publication date: 2 October 2020
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.07497
Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items (5)
The number of satisfying assignments of random 2‐SAT formulas ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ The rank of sparse random matrices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The phase transition in random regular exact cover
- The set of solutions of random XORSAT formulae
- The asymptotic \(k\)-SAT threshold
- NP is as easy as detecting unique solutions
- The 3-XORSAT threshold.
- Information-theoretic thresholds from the cavity method
- Charting the replica symmetric phase
- Two solutions to diluted \(p\)-spin models and XORSAT problems
- On the chromatic number of a random hypergraph
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- Satisfiability Thresholds beyond k −XORSAT
- The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
- Proof of the Satisfiability Conjecture for Large k
- Harnessing the Bethe free energy
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Modern Coding Theory
- Tight Thresholds for Cuckoo Hashing via XORSAT
- Information, Physics, and Computation
- Almost all cubic graphs are Hamiltonian
- Short proofs are narrow—resolution made simple
- The stripping process can be slow: Part I
- A threshold effect for systems of random equations of a special form
- Lossy Source Compression Using Low-Density Generator Matrix Codes: Analysis and Algorithms
- The solution space geometry of random linear equations
- A threshold for unsatisfiability
- On the rank of a random binary matrix
- Cores in random hypergraphs and Boolean formulas
- The Satisfiability Threshold fork-XORSAT
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Satisfiability threshold for random regular \textsc{nae-sat}
This page was built for publication: The satisfiability threshold for random linear equations
