The solution space geometry of random linear equations

DOI10.1002/RSA.20494MaRDI QIDQ4982613zbMATH OpenOpenAlexFDO

Authors

Publication date 9 April 2015

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

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

zbMATH Keywords

coreshypergraphsrandom \(k\)-XORSATsolution clustering

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: We consider random systems of linear equations over GF(2) in which every equation binds k variables. We obtain a precise description of the clustering of solutions in such systems. In particular, we prove that with probability that tends to 1 as the number of variables, n, grows: for every pair of solutions sigma, au, either there exists a sequence of solutions sigma,..., au, in which successive elements differ by O(log n) variables, or every sequence of solutions sigma,..., au, contains a step requiring the simultaneous change of Omega(n) variables. Furthermore, we determine precisely which pairs of solutions are in each category. Our results are tight and highly quantitative in nature. Moreover, our proof highlights the role of unique extendability as the driving force behind the success of Low Density Parity Check codes and our techniques also apply to the problem of so-called pseudo-codewords in such codes.

Recommendations

• Inside the clustering window for random linear equations
• The satisfiability threshold for random linear equations
• Characteristics of random systems of linear equations over a finite field
• A threshold effect for systems of random equations in finite fields
• Geometrical organization of solutions to random linear Boolean equations

Cites work

• A critical point for random graphs with a given degree sequence
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• A simple solution to the k‐core problem
• Component behavior near the critical point of the random graph process
• Cores in random hypergraphs and Boolean formulas
• Information, Physics, and Computation
• Many hard examples for resolution
• On the inherent intractability of certain coding problems (Corresp.)
• On the solution-space geometry of random constraint satisfaction problems
• On tree census and the giant component in sparse random graphs
• Pairs of SAT-assignments in random Boolean formulæ
• Random formulas have frozen variables
• Sudden emergence of a giant k-core in a random graph
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(17)

• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• The satisfiability threshold for random linear equations
• Loose cores and cycles in random hypergraphs
• Probability of unique integer solution to a system of linear equations
• Core forging and local limit theorems for the \(k\)-core of random graphs
• The large deviations of the whitening process in random constraint satisfaction problems
• Inside the clustering window for random linear equations
• Geometrical organization of solutions to random linear Boolean equations
• The satisfiability threshold for k-XORSAT
• The stripping process can be slow. II
• Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs
• The rank of sparse random matrices
• Limits of sequential local algorithms on the random k-XORSAT problem
• The full rank condition for sparse random matrices
• Component games on random graphs
• The k-XORSAT threshold revisited (extended abstract)
• Belief propagation guided decimation on random k-XORSAT

This page was built for publication: The solution space geometry of random linear equations

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