×

The set of solutions of random XORSAT formulae. (English) Zbl 1341.68061

Summary: The XOR-satisfiability (XORSAT) problem requires finding an assignment of \(n\) Boolean variables that satisfy \(m\) exclusive OR (XOR) clauses, whereby each clause constrains a subset of the variables. We consider random XORSAT instances, drawn uniformly at random from the ensemble of formulae containing \(n\) variables and \(m\) clauses of size \(k\). This model presents several structural similarities to other ensembles of constraint satisfaction problems, such as \(k\)-satisfiability (\(k\)-SAT), hypergraph bicoloring and graph coloring. For many of these ensembles, as the number of constraints per variable grows, the set of solutions shatters into an exponential number of well-separated components. This phenomenon appears to be related to the difficulty of solving random instances of such problems.
We prove a complete characterization of this clustering phase transition for random \(k\)-XORSAT. In particular, we prove that the clustering threshold is sharp and determine its exact location. We prove that the set of solutions has large conductance below this threshold and that each of the clusters has large conductance above the same threshold.
Our proof constructs a very sparse basis for the set of solutions (or the subset within a cluster). This construction is intimately tied to the construction of specific subgraphs of the hypergraph associated with an instance of \(k\)-XORSAT. In order to study such subgraphs, we establish novel local weak convergence results for them.

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Achlioptas, D. and Coja-Oghlan, A. (2008). Algorithmic barriers from phase transitions. In Proc. of the 49 th IEEE Symposium on Foundations of Computer Science , FOCS 793-802. IEEE Computer Society, Los Alamitos, CA.
[2] Achlioptas, D., Coja-Oghlan, A. and Ricci-Tersenghi, F. (2011). On the solution-space geometry of random constraint satisfaction problems. Random Structures Algorithms 38 251-268. · Zbl 1217.68156
[3] Achlioptas, D., Naor, A. and Peres, Y. (2005). Rigorous location of phase transitions in hard optimization problems. Nature 435 759-764.
[4] Achlioptas, D. and Peres, Y. (2004). The threshold for random \(k\)-SAT is \(2^{k}\log2-O(k)\). J. Amer. Math. Soc. 17 947-973 (electronic). · Zbl 1093.68075
[5] Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454-1508. · Zbl 1131.60003
[6] Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures (H. Kesten, ed.). Encyclopaedia Math. Sci. 110 1-72. Springer, Berlin. · Zbl 1037.60008
[7] Athreya, K. B. and Ney, P. E. (1972). Branching Processes . Springer, New York. · Zbl 0259.60002
[8] Balogh, J., Peres, Y. and Pete, G. (2006). Bootstrap percolation on infinite trees and non-amenable groups. Combin. Probab. Comput. 15 715-730. · Zbl 1102.60086
[9] Benjamini, I. and Schramm, O. (1996). Percolation beyond \(\mathbf{Z}_{d}\), many questions and a few answers. Electron. Commun. Probab. 1 71-82 (electronic). · Zbl 0890.60091
[10] Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1 311-316. · Zbl 0457.05038
[11] Bollobás, B. (2001). Random Graphs , 2nd ed. Cambridge Studies in Advanced Mathematics 73 . Cambridge Univ. Press, Cambridge. · Zbl 0979.05003
[12] Cocco, S., Dubois, O., Mandler, J. and Monasson, R. (2003). Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices. Phys. Rev. Lett. 90 047205.
[13] Coja-Oghlan, A. (2010). A better algorithm for random \(k\)-SAT. SIAM J. Comput. 39 2823-2864. · Zbl 1209.68345
[14] Dembo, A. and Montanari, A. (2008). Finite size scaling for the core of large random hypergraphs. Ann. Appl. Probab. 18 1993-2040. · Zbl 1152.05051
[15] Dembo, A. and Montanari, A. (2010). Gibbs measures and phase transitions on sparse random graphs. Braz. J. Probab. Stat. 24 137-211. · Zbl 1205.05209
[16] Dembo, A. and Montanari, A. (2010). Ising models on locally tree-like graphs. Ann. Appl. Probab. 20 565-592. · Zbl 1191.82025
[17] Dembo, A., Montanari, A. and Sun, N. (2013). Factor models on locally tree-like graphs. Ann. Probab. 41 4162-4213. · Zbl 1280.05119
[18] Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R. and Rink, M. (2010). Tight thresholds for Cuckoo Hashing via XORSAT. In Proc. of the 37 th International Colloquium on Automata , Languages and Programming , ICALP. Lecture Notes in Computer Science 6198 213-225. Springer, Berlin. · Zbl 1256.68047
[19] Dubhashi, D. P. and Panconesi, A. (2009). Concentration of Measure for the Analysis of Randomized Algorithms . Cambridge Univ. Press, Cambridge. · Zbl 1213.60006
[20] Dubois, O. and Mandler, J. (2002). The 3-XORSAT threshold. In Proc. of the 43 rd IEEE Symposium on Foundations of Computer Science , FOCS 769-778. IEEE Computer Society, Los Alamitos, CA. · Zbl 1038.68052
[21] Friedgut, E. (1999). Sharp thresholds of graph properties, and the \(k\)-sat problem. J. Amer. Math. Soc. 12 1017-1054. · Zbl 0932.05084
[22] Hall, P. (1982). Rates of Convergence in the Central Limit Theorem. Research Notes in Mathematics 62 . Pitman, London. · Zbl 0497.60001
[23] Hoory, S., Linial, N. and Wigderson, A. (2006). Expander graphs and their applications. Bull. Amer. Math. Soc. ( N.S. ) 43 439-561 (electronic). · Zbl 1147.68608
[24] Kallenberg, O. (2002). Foundations of Modern Probability , 2nd ed. Springer, New York. · Zbl 0996.60001
[25] Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W., Gaudry, P., Kruppa, A., Montgomery, P. L., Osvik, D. A., te Riele, H., Timofeev, A. and Zimmermann, P. (2010). Factorization of a 768-bit RSA modulus. In Advances in Cryptology-CRYPTO 2010. Lecture Notes in Computer Science 6223 333-350. Springer, Berlin. · Zbl 1196.11167
[26] Krzakala, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G. and Zdeborová, L. (2007). Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. USA 104 10318-10323 (electronic). · Zbl 1190.68031
[27] Luby, M., Mitzenmacher, M., Shokrollahi, A. and Spielman, D. A. (1998). Analysis of low density codes and improved designs using irregular graphs. In Proc. of the 30 th ACM Symposium on Theory of Computing , STOC 249-258. ACM, New York. · Zbl 0942.68091
[28] Luby, M. G., Mitzenmacher, M., Shokrollahi, M. A. and Spielman, D. A. (2001). Efficient erasure correcting codes. IEEE Trans. Inform. Theory 47 569-584. · Zbl 1019.94032
[29] Mézard, M. and Montanari, A. (2009). Information , Physics , and Computation . Oxford Univ. Press, Oxford. · Zbl 1163.94001
[30] Mézard, M., Parisi, G. and Zecchina, R. (2003). Analytic and algorithmic solution of random satisfiability problems. Science 297 812-815.
[31] Mézard, M., Ricci-Tersenghi, F. and Zecchina, R. (2003). Two solutions to diluted \(p\)-spin models and XORSAT problems. J. Stat. Phys. 111 505-533. · Zbl 1049.82073
[32] Molloy, M. (2005). Cores in random hypergraphs and Boolean formulas. Random Structures Algorithms 27 124-135. · Zbl 1068.05063
[33] Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B. and Troyansky, L. (1999). Determining computational complexity from characteristic “phase transitions”. Nature 400 133-137. · Zbl 0931.68056
[34] Montanari, A. (2013). Statistical mechanics and algorithms on sparse and random graphs. In Lectures on Probability Theory and Statistics . Saint-Flour.
[35] Pittel, B., Spencer, J. and Wormald, N. (1996). Sudden emergence of a giant \(k\)-core in a random graph. J. Combin. Theory Ser. B 67 111-151. · Zbl 0860.05065
[36] Richardson, T. and Urbanke, R. (2008). Modern Coding Theory . Cambridge Univ. Press, Cambridge. · Zbl 1188.94001
[37] Wormald, N. C. (1981). The asymptotic distribution of short cycles in random regular graphs. J. Combin. Theory Ser. B 31 168-182. · Zbl 0442.05042
[38] Wormald, N. C. (1999). Models of random regular graphs. In Surveys in Combinatorics , 1999 ( Canterbury ) (J. D. Lamb and D. A. Preece, eds.). London Mathematical Society Lecture Note Series 267 239-298. Cambridge Univ. Press, Cambridge. · Zbl 0935.05080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.