Name
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 one to study the 'x-satisfiability' threshold, the critical density of equations where there exist two solutions at a given distance. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1088/1742-5468/2006/10/P10007 | JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT |
Keywords | DocType | Volume |
cavity and replica method,message-passing algorithms,typical case computational complexity | Journal | abs/cond-m |
Issue | ISSN | Citations |
10 | 1742-5468 | 7 |
PageRank | References | Authors |
0.72 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thierry Mora | 1 | 24 | 7.98 |
| Marc Mézard | 2 | 590 | 39.09 |