The set of solutions of random XORSAT formulae

MaRDI QIDQ5743435zbMATH OpenFDO

Authors Morteza Ibrahimi, Yashodhan Kanoria, Matt Kraning, Andrea Montanari

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095178

Mathematics Subject Classification ID

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

Recommendations

• The set of solutions of random XORSAT formulae
• Solution clustering in random satisfiability
• Inside the clustering window for random linear equations
• Geometrical organization of solutions to random linear Boolean equations
• Reconstruction and clustering in random constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• scientific article; zbMATH DE number 1775410 (Why is no real title available?)
• A better algorithm for random \(k\)-SAT
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Cores in random hypergraphs and Boolean formulas
• Determining computational complexity from characteristic ``phase transitions
• Efficient erasure correcting codes
• Expander graphs and their applications
• Factorization of a 768-Bit RSA Modulus
• Finite size scaling for the core of large random hypergraphs
• Gibbs measures and phase transitions on sparse random graphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Information, Physics, and Computation
• Modern Coding Theory
• On the solution-space geometry of random constraint satisfaction problems
• Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers
• Processes on unimodular random networks
• Random graphs.
• Sharp thresholds of graph properties, and the $k$-sat problem
• The 3-XORSAT threshold.
• The asymptotic distribution of short cycles in random regular graphs
• The set of solutions of random XORSAT formulae
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(7)

• Solution clustering in random satisfiability
• The set of solutions of random XORSAT formulae
• Two solutions to diluted p-spin models and XORSAT problems
• The set of solutions of random XORSAT formulae
• Inside the clustering window for random linear equations
• Geometrical organization of solutions to random linear Boolean equations
• Satisfiability thresholds beyond \(k\)-XORSAT

This page was built for publication: The set of solutions of random XORSAT formulae

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743435)