Catching the k-NAESAT threshold
From MaRDI portal
Publication:5415523
DOI10.1145/2213977.2214058zbMath1286.68185arXiv1111.1274OpenAlexW2132891419MaRDI QIDQ5415523
Amin Coja-Oghlan, Konstantinos D. Panagiotou
Publication date: 13 May 2014
Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.1274
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (22)
Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ On the number of solutions in random hypergraph 2-colouring ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Statistical limits of spiked tensor models ⋮ On the chromatic number of random regular graphs ⋮ Combinatorial statistics and the sciences ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ 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 ⋮ Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem ⋮ Random hypergraphs and property B ⋮ Phase Transition for Maximum Not-All-Equal Satisfiability ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Spin systems on Bethe lattices ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ 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 ⋮ Non‐orderability of random triangular groups by using random 3CNF formulas
This page was built for publication: Catching the k-NAESAT threshold
