The set of solutions of random XORSAT formulae

DOI10.1214/14-AAP1060zbMath1341.68061arXiv1107.5377MaRDI QIDQ748322

Morteza Ibrahimi, Yash Kanoria, Matt Kraning, Andrea Montanari

Publication date: 20 October 2015

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.5377

zbMATH Keywords

phase transitionrandom graphlocal weak convergencebelief propagationclustering of solutionsrandom constraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Right-convergence of sparse random graphs, Network models: structure and function. Abstracts from the workshop held December 10--16, 2017, The large deviations of the whitening process in random constraint satisfaction problems, The satisfiability threshold for random linear equations, The Stripping Process Can be Slow: Part II, Core forging and local limit theorems for the \(k\)-core of random graphs, Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs, The rank of sparse random matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite size scaling for the core of large random hypergraphs
• Ising models on locally tree-like graphs
• Gibbs measures and phase transitions on sparse random graphs
• The asymptotic distribution of short cycles in random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers
• The 3-XORSAT threshold.
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Sudden emergence of a giant \(k\)-core in a random graph
• Factor models on locally tree-like graphs
• Processes on unimodular random networks
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Modern Coding Theory
• Expander graphs and their applications
• Factorization of a 768-Bit RSA Modulus
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Information, Physics, and Computation
• Sharp thresholds of graph properties, and the $k$-sat problem
• Efficient erasure correcting codes
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Cores in random hypergraphs and Boolean formulas
• Gibbs states and the set of solutions of random constraint satisfaction problems
• A Better Algorithm for Random k-SAT
• On the solution‐space geometry of random constraint satisfaction problems
• Concentration of Measure for the Analysis of Randomized Algorithms