The k-XORSAT threshold revisited

EUROCOMB’23

Abstract
We provide a simplified proof of the random $k$-XORSAT satisfiability threshold theorem. As an extension we also determine the full rank threshold for sparse random matrices over finite fields with precisely $k$ non-zero entries per row. This complements a result from [Ayre, Coja-Oghlan, Gao, Müller: Combinatorica 2020]. The proof combines physics-inspired message passing arguments with a surgical moment computation. Msc: 60B20, 15B52

Pages:
298–304
References

Achlioptas, D., Molloy, M.: The solution space geometry of random linear equations. Random Structures and Algorithms 46 (2015) 197-231.
https://doi.org/10.1002/rsa.20494

Achlioptas, D., Naor, A., Peres, Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435, 759-764.
https://doi.org/10.1038/nature03602

Aizenman, M., Sims, R., Starr, S.: An extended variational principle for the SK spin-glass model. Phys. Rev. B 68 (2003) 214403.
https://doi.org/10.1103/PhysRevB.68.214403

Ayre, P., Coja-Oghlan, A., Gao, P., Müller, N.: The satisfiability threshold for random linear equations. Combinatorica 40 (2020) 179-235.
https://doi.org/10.1007/s00493-019-3897-3

Coja-Oghlan, A., Cooley, O., Kang, M., Lee, J., Ravelomanana, J.: The sparse parity matrix. Proc. 33rd SODA (2022) 822-833.
https://doi.org/10.1137/1.9781611977073.35

Coja-Oghlan, A., Gao, P., Hahn-Klimroth, M., Lee, J., Müller, N., Rolvien, M.: The full rank condition for sparse random matrices. arXiv 2112.14090 (2021).
https://doi.org/10.1137/1.9781611975994.35

Coja-Oghlan, A., Ergür, A., Gao, P., Hetterich, S., Rolvien, M.: The rank of sparse random matrices. Proc. 31st SODA (2020) 579-591.
https://doi.org/10.1137/1.9781611975994.35

Cooley, O., Lee, J., Ravelomanana, J.: Warning Propagation: stability and subcriticality. arXiv:2111.15577 (2021).

Cooper, C.: The cores of random hypergraphs with a given degree sequence. Random Structures and Algorithms 25 (2004) 353-375.
https://doi.org/10.1002/rsa.20040

Cooper, C., Frieze, A., Pegden, W.: On the rank of a random binary matrix. Electron. J. Comb. 26 (2019) P4.12.
https://doi.org/10.37236/8092

Creignou, N., Daude, H., Dubois, O.: Approximating the satisfiability threshold for random k-XOR-formulas. arXiv:cs/0106001 (2001).

Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight thresholds for cuckoo hashing via XORSAT. Proc. 37th ICALP (2010) 213-225.
https://doi.org/10.1007/978-3-642-14165-2_19

Ding, J., Sly, A., Sun, N.: Proof of the satisfiability conjecture for large k. Annals of Mathematics 196 (2022) 1-388.
https://doi.org/10.4007/annals.2022.196.1.1

Dubois, O., Mandler, J.: The 3-XORSAT threshold. Proc. 43rd FOCS (2002) 769-778.
https://doi.org/10.1016/S1631-073X(02)02563-3

Fernholz, D., Ramachandran, V.: Cores and connectivity in sparse random graphs. UTCS Technical Report TR04-13 (2004).

Goerdt, A., Falke, L.: Satisfiability thresholds beyond k-XORSAT. Proc. 7th International Computer Science Symposium in Russia (2012) 148-159.
https://doi.org/10.1007/978-3-642-30642-6_15

Ibrahimi, M., Kanoria, Y., Kraning, M., Montanari, A.: The set of solutions of random XORSAT formulae. Annals of Applied Probability 25 (2015) 2743-2808.
https://doi.org/10.1214/14-AAP1060

Janson, S., Luczak, M.: A simple solution to the k-core problem. Random Structures and Algorithms 30 (2007) 50-62.
https://doi.org/10.1002/rsa.20147

Janson, S., Luczak, T., Rucinski, A.: Random graphs. Wiley (2000).
https://doi.org/10.1002/9781118032718

Kim, J.H.: Poisson cloning model for random graphs. Proceedings of the International Congress of Mathematicians (2006) 873-897.
https://doi.org/10.4171/022-3/43

Mézard, M., Montanari, A.: Information, physics and computation. Oxford University Press (2009).
https://doi.org/10.1093/acprof:oso/9780198570837.001.0001

Mézard, M., Ricci-Tersenghi, F., Zecchina, R.: Two solutions to diluted p-spin models and XORSAT problems. Journal of Statistical Physics 111 (2003) 505-533.
https://doi.org/10.1023/A:1022886412117

Molloy, M.: Cores in random hypergraphs and Boolean formulas. Random Structures and Algorithms 27 (2005) 124-135.
https://doi.org/10.1002/rsa.20061

Montanari, A.: Estimating random variables from random sparse observations. European Transactions on Telecommunications 19(4) (2008) 385-403.
https://doi.org/10.1002/ett.1289

Panchenko, D., Talagrand, M.: Bounds for diluted mean-fields spin glass models. Probab. Theory Relat. Fields 130 (2004) 319-336.
https://doi.org/10.1007/s00440-004-0342-2

Pittel, B., Sorkin, G.: The satisfiability threshold for k-XORSAT. CPC 25 (2016) 236-268.
https://doi.org/10.1017/S0963548315000097

Pittel, B., Spencer, J., Wormald, N.: Sudden emergence of a giant k-core in a random graph. Journal of Combinatorial Theory, Series B 67 (1996) 111-151.
https://doi.org/10.1006/jctb.1996.0036

Raghavendra, P., Tan, N.: Approximating CSPs with global cardinality constraints using SDP hierarchies. Proc. 23rd SODA (2012) 373-387.
https://doi.org/10.1137/1.9781611973099.33

Riordan, O.: The k-core and branching processes. Combinatorics, Probability and Computing 17 (2008) 111-136.
https://doi.org/10.1017/S0963548307008589

Metrics

0

Views

0

PDF views