The k-XORSAT threshold revisited
EUROCOMB’23
298–304
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

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien