Geometrical organization of solutions to random linear Boolean equations

Abstract

The random XORSAT problem deals with large random linear systems of Boolean variables. The difficulty of such problems is controlled by the ratio of number of equations to number of variables. It is known that in some range of values of this parameter, the space of solutions breaks into many disconnected clusters. Here we study precisely the corresponding geometrical organization. In particular, the distribution of distances between these clusters is computed by the cavity method. This allows to study the `x-satisfiability' threshold, the critical density of equations where there exist two solutions at a given distance.

20 pages

References in corpus (5)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• Coloring random graphs
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Landscape of solutions in constraint satisfaction problems

Cited by in corpus (13)

• On the freezing of variables in random constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Pairs of SAT Assignment in Random Boolean Formulae
• Random subcubes as a toy model for constraint satisfaction problems
• Statistical Mechanics of maximal independent sets
• Entropy landscape of solutions in the binary perceptron problem
• Belief propagation for graph partitioning
• Statistical physics approach to graphical games: local and global interactions
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Barriers and local minima in energy landscapes of stochastic local search
• Inside the clustering threshold for random linear equations
• Typical rank of coin-toss power-law random matrices over GF(2)