The set of solutions of random XORSAT formulae

zbMATH Open1423.68211MaRDI QIDQ5743435FDOQ5743435

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

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

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)

Cites Work

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

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)