Inside the clustering window for random linear equations

DOI10.1002/RSA.20740MaRDI QIDQ4564856zbMATH OpenOpenAlexFDO

Authors

Publication date 7 June 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

clustering thresholdcritical windowphase transitionrandom XORSATsolution geometry

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Linear equations (linear algebraic aspects) (15A06) Combinatorial probability (60C99)

Abstract: We study a random system of cn linear equations over n variables in GF(2), where each equation contains exactly r variables; this is equivalent to r-XORSAT. Previous work has established a clustering threshold, c^*_r for this model: if c=c_r^*-epsilon for any constant epsilon>0 then with high probability all solutions form a well-connected cluster; whereas if c=c^*_r+epsilon, then with high probability the solutions partition into well-connected, well-separated clusters (with probability tending to 1 as n goes to infinity). This is part of a general clustering phenomenon which is hypothesized to arise in most of the commonly studied models of random constraint satisfaction problems, via sophisticated but mostly non-rigorous techniques from statistical physics. We extend that study to the range c=c^*_r+o(1), and prove that the connectivity parameters of the r-XORSAT clusters undergo a smooth transition around the clustering threshold.

Recommendations

• The set of solutions of random XORSAT formulae
• The solution space geometry of random linear equations
• Geometrical organization of solutions to random linear Boolean equations
• The set of solutions of random XORSAT formulae
• Solution clustering in random satisfiability

Cited in

(6)

• Geometrical organization of solutions to random linear Boolean equations
• The solution space geometry of random linear equations
• The set of solutions of random XORSAT formulae
• The stripping process can be slow. II
• On the thresholds in linear and nonlinear Boolean equations
• The set of solutions of random XORSAT formulae

This page was built for publication: Inside the clustering window for random linear equations

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