The 3-XORSAT threshold

Olivier Dubois; Jacques Mandler

doi:10.1016/S1631-073X(02)02563-3

The 3-XORSAT threshold
[Le seuil de 3-XORSAT]

Olivier Dubois ¹ ; Jacques Mandler ¹

¹ LIP6, Box 169, CNRS-Université Paris 6, 4 place Jussieu, 75252 Paris cedex 05, France

Comptes Rendus. Mathématique, Volume 335 (2002) no. 11, pp. 963-966.

Abstract (VO)
Résumé

We prove the existence of a threshold phenomenon regarding the random 3-XORSAT problem (or more generally k-XORSAT). We provide the value of the threshold as the solution of two transcendental equations. These results confirm rigorously those obtained by physicists using the one-step replica symmetry breaking method and thus give for the first time the proof of the validity of this method for a problem of the class of satisfiability problems.

Nous démontrons l'existence d'un phénomène de seuil pour le problème 3-XORSAT aléatoire (et plus généralement k-XORSAT). Nous fournissons la valeur du seuil comme solution de deux équations transcendantes. Ces résultats confirment rigoureusement ceux obtenus par des physiciens au moyen de la méthode des répliques à un pas de brisure de symétrie et apportent ainsi pour la première fois une preuve de la validité de la méthode des répliques avec brisure sur un problème de la classe des problèmes de satisfaisabilité.

Reçu le : 2002-08-20
Accepté le : 2002-09-13
Publié le : 2002-10-05

DOI : 10.1016/S1631-073X(02)02563-3

Affiliations des auteurs :

Olivier Dubois ¹ ; Jacques Mandler ¹

¹ LIP6, Box 169, CNRS-Université Paris 6, 4 place Jussieu, 75252 Paris cedex 05, France

@article{CRMATH_2002__335_11_963_0,
     author = {Olivier Dubois and Jacques Mandler},
     title = {The {3-XORSAT} threshold},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {963--966},
     publisher = {Elsevier},
     volume = {335},
     number = {11},
     year = {2002},
     doi = {10.1016/S1631-073X(02)02563-3},
     language = {en},
}

TY  - JOUR
AU  - Olivier Dubois
AU  - Jacques Mandler
TI  - The 3-XORSAT threshold
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 963
EP  - 966
VL  - 335
IS  - 11
PB  - Elsevier
DO  - 10.1016/S1631-073X(02)02563-3
LA  - en
ID  - CRMATH_2002__335_11_963_0
ER  -

%0 Journal Article
%A Olivier Dubois
%A Jacques Mandler
%T The 3-XORSAT threshold
%J Comptes Rendus. Mathématique
%D 2002
%P 963-966
%V 335
%N 11
%I Elsevier
%R 10.1016/S1631-073X(02)02563-3
%G en
%F CRMATH_2002__335_11_963_0

Olivier Dubois; Jacques Mandler. The 3-XORSAT threshold. Comptes Rendus. Mathématique, Volume 335 (2002) no. 11, pp. 963-966. doi : 10.1016/S1631-073X(02)02563-3. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(02)02563-3/

Bibliographie
Cité par

[1] A.Z. Broder; A.M. Frieze; E. Upfal On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, Austin, TX, 1993, pp. 322-330

[2] N. Creignou, H. Daudé, O. Dubois, Approximating the satisfiability threshold for random k-XOR-formulas, 2001, submitted

[3] S. Franz; M. Leone; F. Ricci-Tersenghi; R. Zecchina Phys. Rev. Lett., 87 (2001), pp. 12713-127209

[4] R. Monasson, personal communication

[5] M. Talagrand, Spin Glasses: A Challenge for Mathematicians, in preparation

[6] N.M. Temme Asymptotic estimates of Stirling numbers, Studies Appl. Math., Volume 89 (1993), pp. 233-243

[7] N.C. Wormald Differential equations for random processes and random graphs, Ann. Appl. Probab., Volume 5 (1995), pp. 1217-1235

Remco van der Hofstad; Noela Müller; Haodong Zhu The rank of sparse symmetric matrices over arbitrary fields, Random Structures Algorithms, Volume 66 (2025) no. 1, p. 66 (Id/No e21258) | DOI:10.1002/rsa.21258 | Zbl:1557.05156
Danny Nam; Allan Sly; Youngtak Sohn One-step replica symmetry breaking of random regular NAE-SAT. II, Communications in Mathematical Physics, Volume 405 (2024) no. 3, p. 63 (Id/No 61) | DOI:10.1007/s00220-023-04868-6 | Zbl:7811482
Ashwin Sah; Mehtaab Sawhney, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (2023), p. 2369 | DOI:10.1109/focs57990.2023.00145
Amin Coja-Oghlan; Mihyun Kang; Lena Krieg; Maurice Rolvien, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (2023), p. 298 | DOI:10.5817/cz.muni.eurocomb23-041
Rui Ding; Shibo Yang; Xiang Chen; Qun Huang, Proceedings of the ACM SIGCOMM 2023 Conference (2023), p. 220 | DOI:10.1145/3603269.3604865
Amin Coja‐Oghlan; Alperen A. Ergür; Pu Gao; Samuel Hetterich; Maurice Rolvien The rank of sparse random matrices, Random Structures Algorithms, Volume 62 (2023) no. 1, p. 68 | DOI:10.1002/rsa.21085
Peter Ayre; Amin Coja-Oghlan; Catherine Greenhill Lower bounds on the chromatic number of random graphs, Combinatorica, Volume 42 (2022) no. 5, pp. 617-658 | DOI:10.1007/s00493-021-4236-z | Zbl:1524.05283
M. Bernaschi; M. Bisson; M. Fatica; E. Marinari; V. Martin-Mayor; G. Parisi; F. Ricci-Tersenghi How we are leading a 3-XORSAT challenge: From the energy landscape to the algorithm and its efficient implementation on GPUs (a), Europhysics Letters, Volume 133 (2021) no. 6, p. 60005 | DOI:10.1209/0295-5075/133/60005
Matteo Bellitti; Federico Ricci-Tersenghi; Antonello Scardicchio Entropic barriers as a reason for hardness in both classical and quantum algorithms, Physical Review Research, Volume 3 (2021) no. 4 | DOI:10.1103/physrevresearch.3.043015
Dimitris Achlioptas; Amin Coja-Oghlan; Max Hahn-Klimroth; Joon Lee; Noëla Müller; Manuel Penschuck; Guangyan Zhou The number of satisfying assignments of random 2-SAT formulas, Random Structures Algorithms, Volume 58 (2021) no. 4, pp. 609-647 | DOI:10.1002/rsa.20993 | Zbl:1522.68375
Peter Ayre; Amin Coja-Oghlan; Pu Gao; Noëla Müller The satisfiability threshold for random linear equations, Combinatorica, Volume 40 (2020) no. 2, pp. 179-235 | DOI:10.1007/s00493-019-3897-3 | Zbl:1463.05507
Amin Coja-Oghlan; Tobias Kapetanopoulos; Noela Müller The replica symmetric phase of random constraint satisfaction problems, Combinatorics, Probability and Computing, Volume 29 (2020) no. 3, pp. 346-422 | DOI:10.1017/s0963548319000440 | Zbl:1504.68152
Harold Connamacher; Julia Dobrosotskaya On the uniformity of the approximation for $r$ -associated Stirling numbers of the second kind, Contributions to Discrete Mathematics, Volume 15 (2020) no. 3, pp. 25-42 | DOI:10.11575/cdm.v15i3.68674 | Zbl:1493.11051
Marco Genuzio; Giuseppe Ottaviano; Sebastiano Vigna Fast scalable construction of ([compressed] static | minimal perfect hash) functions, Information and Computation, Volume 273 (2020), p. 17 (Id/No 104517) | DOI:10.1016/j.ic.2020.104517 | Zbl:1446.68038
Watts Adam Bene; Aram W. Harrow; Gurtej Kanwar; Anand Natarajan Algorithms, bounds, and strategies for entangled XOR games, 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA, Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2019, p. 18 (Id/No 10) | DOI:10.4230/lipics.itcs.2019.10 | Zbl:1542.68064
Martin Dietzfelbinger; Stefan Walzer Dense peelable random uniform hypergraphs, 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings, Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019, p. 16 (Id/No 38) | DOI:10.4230/lipics.esa.2019.38 | Zbl:1547.68577
Amin Coja-Oghlan; Oliver Gebhard; Max Hahn-Klimroth; Philipp Loick Information-theoretic and algorithmic thresholds for group testing, 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings, Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019, p. 14 (Id/No 43) | DOI:10.4230/lipics.icalp.2019.43 | Zbl:1552.62053
Colin Cooper; Alan Frieze; Wesley Pegden Minors of a random binary matroid, Random Structures Algorithms, Volume 55 (2019) no. 4, pp. 865-880 | DOI:10.1002/rsa.20881 | Zbl:1433.05276
Marco Genuzio; Sebastiano Vigna, 2018 Data Compression Conference (2018), p. 52 | DOI:10.1109/dcc.2018.00013
Pu Gao; Michael Molloy Inside the clustering window for random linear equations, Random Structures Algorithms, Volume 52 (2018) no. 2, pp. 197-218 | DOI:10.1002/rsa.20740 | Zbl:1396.60008
Subhabrata Sen Optimization on sparse random hypergraphs and spin glasses, Random Structures Algorithms, Volume 53 (2018) no. 3, pp. 504-536 | DOI:10.1002/rsa.20774 | Zbl:1397.05121
Jun Takahashi; Satoshi Takabe; Koji Hukushima An Exact Algorithm Exhibiting RS–RSB/Easy–Hard Correspondence for the Maximum Independent Set Problem, Journal of the Physical Society of Japan, Volume 86 (2017) no. 7, p. 073001 | DOI:10.7566/jpsj.86.073001
Louigi Addario-Berry; Shankar Bhamidi; Remco van der Hofstad; Frank den Hollander Network models: structure and function. Abstracts from the workshop held December 10–16, 2017, Oberwolfach Rep. 14, No. 4, 3427-3470, 2017 | DOI:10.4171/owr/2017/57 | Zbl:1409.00060
Amin Coja-Oghlan; Konstantinos Panagiotou The asymptotic $k$ -SAT threshold, Advances in Mathematics, Volume 288 (2016), pp. 985-1068 | DOI:10.1016/j.aim.2015.11.007 | Zbl:1394.60007
Boris Pittel; Gregory B. Sorkin The satisfiability threshold for $k$ -XORSAT, Combinatorics, Probability and Computing, Volume 25 (2016) no. 2, pp. 236-268 | DOI:10.1017/s0963548315000097 | Zbl:1372.68193
Guangyan Zhou; Zongsheng Gao; Jun Liu The scaling window of the model $d$ - $k$ -CSP, Journal of Mathematical Analysis and Applications, Volume 434 (2016) no. 1, pp. 342-352 | DOI:10.1016/j.jmaa.2015.09.015 | Zbl:1334.82035
Eleanor G. Rieffel; Davide Venturelli; Bryan O'Gorman; Minh B. Do; Elicia M. Prystay; Vadim N. Smelyanskiy A case study in programming a quantum annealer for hard operational planning problems, Quantum Information Processing, Volume 14 (2015) no. 1, pp. 1-36 | DOI:10.1007/s11128-014-0892-x | Zbl:1311.81084
Morteza Ibrahimi; Yash Kanoria; Matt Kraning; Andrea Montanari The set of solutions of random XORSAT formulae, The Annals of Applied Probability, Volume 25 (2015) no. 5, pp. 2743-2808 | DOI:10.1214/14-aap1060 | Zbl:1341.68061
Richard Darling; Mathew Penrose; Andrew Wade; Sandy Zabell Rank deficiency in sparse random GF $[2]$ matrices, Electronic Journal of Probability, Volume 19 (2014) no. none | DOI:10.1214/ejp.v19-2458
Amin Coja-Oghlan Upper-bounding the $k$ -colorability threshold by counting covers, The Electronic Journal of Combinatorics, Volume 20 (2013) no. 3, p. research | Zbl:1298.05285
Andreas Goerdt; Lutz Falke Satisfiability thresholds beyond $k$ -XORSAT, Computer science – theory and applications. 7th international computer science symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3–7, 2012. Proceedings, Berlin: Springer, 2012, pp. 148-159 | DOI:10.1007/978-3-642-30642-6_15 | Zbl:1360.68779
Amin Coja-Oghlan; Lenka Zdeborová The condensation transition in random hypergraph 2-coloring, Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012., Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM), 2012, pp. 241-250 | Zbl:1421.68068
Hervé Daudé; Conrado Martínez; Vonjy Rasendrahasina; Vlady Ravelomanana The MAX-CUT of sparse random graphs, Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012., Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM), 2012, pp. 265-271 | Zbl:1423.05150
Morteza Ibrahimi; Yashodhan Kanoria; Matt Kraning; Andrea Montanari The set of solutions of random XORSAT formulae, Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012., Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM), 2012, pp. 760-779 | Zbl:1423.68211
Alan Frieze; Páll Melsted Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables, Random Structures Algorithms, Volume 41 (2012) no. 3, pp. 334-364 | DOI:10.1002/rsa.20427 | Zbl:1252.05175
Harold Connamacher; Michael Molloy The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem, SIAM Journal on Discrete Mathematics, Volume 26 (2012) no. 2, p. 768 | DOI:10.1137/090777268
Harold Connamacher Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, Theoretical Computer Science, Volume 421 (2012), pp. 25-55 | DOI:10.1016/j.tcs.2011.11.014 | Zbl:1280.68237
Daudé Hervé; Ravelomanana Vlady Random 2 XORSAT phase transition, Algorithmica, Volume 59 (2011) no. 1, pp. 48-65 | DOI:10.1007/s00453-009-9308-1 | Zbl:1206.68285
Michael Molloy When does the giant component bring unsatisfiability?, Combinatorica, Volume 28 (2008) no. 6, pp. 693-734 | DOI:10.1007/s00493-008-2123-5 | Zbl:1195.05077
Thierry Mora; Lenka Zdeborová Random subcubes as a toy model for constraint satisfaction problems, Journal of Statistical Physics, Volume 131 (2008) no. 6, pp. 1121-1138 | DOI:10.1007/s10955-008-9543-x | Zbl:1214.82045
Hamed Hatami; Michael Molloy Sharp thresholds for constraint satisfaction problems and homomorphisms, Random Structures Algorithms, Volume 33 (2008) no. 3, pp. 310-332 | DOI:10.1002/rsa.20225 | Zbl:1182.05110
Hervé Daudé; Marc Mézard; Thierry Mora; Riccardo Zecchina Pairs of SAT-assignments in random Boolean formulæ, Theoretical Computer Science, Volume 393 (2008) no. 1-3, pp. 260-279 | DOI:10.1016/j.tcs.2008.01.005 | Zbl:1136.68049
Gilles Dequen; Olivier Dubois An efficient approach to solving random $k$ -SAT problems, Journal of Automated Reasoning, Volume 37 (2006) no. 4, pp. 261-276 | DOI:10.1007/s10817-006-9025-2 | Zbl:1113.68099
Thierry Mora; Marc Mézard Geometrical organization of solutions to random linear Boolean equations, Journal of Statistical Mechanics: Theory and Experiment, Volume 2006 (2006) no. 10, p. 21 (Id/No p10007) | DOI:10.1088/1742-5468/2006/10/p10007 | Zbl:1456.94146
Alan Frieze; Michael Molloy The satisfiability threshold for randomly generated binary constraint satisfaction problems, Random Structures Algorithms, Volume 28 (2006) no. 3, p. 323 | DOI:10.1002/rsa.20118
Ke Xu; Wei Li Many hard examples in exact phase transitions, Theoretical Computer Science, Volume 355 (2006) no. 3, pp. 291-302 | DOI:10.1016/j.tcs.2006.01.001 | Zbl:1088.68163
Nadia Creignou; Hervé Daudé Combinatorial sharpness criterion and phase transition classification for random CSPs, Information and Computation, Volume 190 (2004) no. 2, pp. 220-238 | DOI:10.1016/j.ic.2004.01.002 | Zbl:1085.68151
Don Coppersmith; David Gamarnik; Mohammad Taghi Hajiaghayi; Gregory B. Sorkin Random MAX SAT, random MAX CUT, and their phase transitions, Random Structures Algorithms, Volume 24 (2004) no. 4, pp. 502-545 | DOI:10.1002/rsa.20015 | Zbl:1077.68118

Cité par 48 documents. Sources : Crossref, zbMATH

Commentaires - Politique