Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-07T03:35:29.268Z Has data issue: false hasContentIssue false
  • English
  • Français

The Satisfiability Threshold for k-XORSAT

Part of: Theory of computing Probability theory on algebraic and topological structures Combinatorics

Published online by Cambridge University Press:  31 July 2015

BORIS PITTEL  and
GREGORY B. SORKIN
BORIS PITTEL
Affiliation:
Department of Mathematics, Ohio State University, Columbus OH 43210, USA (e-mail: bgp@math.ohio-state.edu)
GREGORY B. SORKIN
Affiliation:
Departments of Management and Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK (e-mail: g.b.sorkin@lse.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider ‘unconstrained’ random k-XORSAT, which is a uniformly random system of m linear non-homogeneous equations in $\mathbb{F}$2 over n variables, each equation containing k ⩾ 3 variables, and also consider a ‘constrained’ model where every variable appears in at least two equations. Dubois and Mandler proved that m/n = 1 is a sharp threshold for satisfiability of constrained 3-XORSAT, and analysed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT.

We show that m/n = 1 remains a sharp threshold for satisfiability of constrained k-XORSAT for every k ⩾ 3, and we use standard results on the 2-core of a random k-uniform hypergraph to extend this result to find the threshold for unconstrained k-XORSAT. For constrained k-XORSAT we narrow the phase transition window, showing that m − n → −∞ implies almost-sure satisfiability, while m − n → +∞ implies almost-sure unsatisfiability.

MSC classification

Primary: 68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Secondary: 60B20: Random matrices (probabilistic aspects; for algebraic aspects see ) 05A16: Asymptotic enumeration
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 2 , March 2016 , pp. 236 - 268
Copyright
Copyright © Cambridge University Press 2015 

References

[1] Achlioptas, D. and Molloy, M. (2015) The solution space geometry of random linear equations. Random Struct. Alg. 46 197–231.Google Scholar
[2] Aronson, J., Frieze, A. and Pittel, B. (1998) On maximum matching in sparse random graphs: Karp–Sipser revisited. Random Struct. Alg. 12 111–177.3.0.CO;2-#>CrossRefGoogle Scholar
[3] Balister, P. (2012) Personal communication.Google Scholar
[4] Blömer, J., Karp, R. and Welzl, E. (1997) The rank of sparse random matrices over finite fields. Random Struct. Alg. 10 407–419.Google Scholar
[5] Bollobás, B., Borgs, C., Chayes, J. T., Kim, J.-H. and Wilson, D. B. (2001) The scaling window of the 2-SAT transition. Random Struct. Alg. 18 201–256.CrossRefGoogle Scholar
[6] de Bruijn, N. G. (1981) Asymptotic Methods in Analysis, Dover.Google Scholar
[7] Chvátal, V. and Reed, B. (1992) Mick gets some (the odds are on his side). In 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 620–627.Google Scholar
[8] Cooper, C. (2000) On the rank of random matrices. Random Struct. Alg. 16 209–232.Google Scholar
[9] Cooper, C. (2004) The cores of random hypergraphs with a given degree sequence. Random Struct. Alg. 25 353–375.Google Scholar
[10] Coppersmith, D., Gamarnik, D., Hajiaghayi, M. T. and Sorkin, G. B. (2004) Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct. Alg. 24 502–545.Google Scholar
[11] Creignon, N. and Daudé, H. (2003) Smooth and sharp thresholds for random k-XOR-CNF satisfiability. Theor. Inform. Appl. 37 127–147.CrossRefGoogle Scholar
[12] Darling, R. W. R., Penrose, M. D., Wade, A. R. and Zabell, S. L. (2014) Rank deficiency in sparse random GF[2] matrices. Electron. J. Probab. 19, 2458 (Paper 83).Google Scholar
[13] Daudé, H. and Ravelomanana, V. (2008) Random 2-XORSAT at the satisfiability threshold. In LATIN 2008: Theoretical Informatics, Vol. 4957 of Lecture Notes in Computer Science, Springer, pp. 12–23.Google Scholar
[14] Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R. and Rink, M. (2010) Tight thresholds for cuckoo hashing via XORSAT. In Proc. 37th International Colloquium on Automata, Languages and Programming: ICALP'10 (Abramsky, S. et al., eds), Springer, pp. 213–225.Google Scholar
[15] Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R. and Rink, M. (2010) Tight thresholds for cuckoo hashing via XORSAT. arXiv:0912.0287v3 Google Scholar
[16] Dubois, O. and Mandler, J. (2002) The 3-XORSAT threshold. In Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science: FOCS 2002, IEEE Computer Society, pp. 769–778.CrossRefGoogle Scholar
[17] Dubois, O. and Mandler, J. (2002) The 3-XORSAT threshold. CR Acad. Sci. Paris, Ser. I 335 963–966.Google Scholar
[18] Fernandez de la Vega, W. (1992) On random 2-SAT. Manuscript.Google Scholar
[19] Friedgut, E. (1999) Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc. 12 1017–1054.Google Scholar
[20] Goerdt, A. (1996) A threshold for unsatisfiability. J. Comput. System Sci. 53 469–486.CrossRefGoogle Scholar
[21] Kim, J. H. (2006) Poisson cloning model for random graphs, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 873–897.Google Scholar
[22] Kolchin, V. F. (1999) Random Graphs , Vol. 53 of Encyclopedia of Mathematics and its Applications, Cambridge University Press.Google Scholar
[23] Mézard, M., Ricci-Tersenghi, F. and Zecchina, R. (2003) Two solutions to diluted p-spin models and XORSAT problems. J. Statist. Phys. 111 505–533.Google Scholar
[24] Mézard, M., Ricci-Tersenghi, F. and Zecchina, R. (2014) Personal communication.Google Scholar
[25] Molloy, M. (2005) Cores in random hypergraphs and Boolean formulas. Random Struct. Alg. 27 124–135.Google Scholar
[26] Pittel, B. (1986) Paths in a random digital tree: Limiting distributions. Adv. Appl. Probab. 18 139–155.Google Scholar
[27] Pittel, B. and Sorkin, G. B. (2012) The satisfiability threshold for k-XORSAT. arXiv:1212.1905v1 Google Scholar
[28] Pittel, B. and Sorkin, G. B. (2012) The satisfiability threshold for k-XORSAT, using an alternative proof. arXiv:1212.3822 Google Scholar
[29] 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.Google Scholar
[30] Pittel, B. and Yeum, J.-A. (2010) How frequently is a system of 2-linear equations solvable? Electron. J. Combin. 17 R92.Google Scholar
[31] Thompson, C. J. (1972) Mathematical Statistical Mechanics, Macmillan.Google Scholar