{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T08:00:53Z","timestamp":1772265653374,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00493-019-3897-3","type":"journal-article","created":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T06:12:50Z","timestamp":1583302370000},"page":"179-235","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The Satisfiability Threshold For Random Linear Equations"],"prefix":"10.1007","volume":"40","author":[{"given":"Peter","family":"Ayre","sequence":"first","affiliation":[]},{"given":"Amin","family":"Coja-Oghlan","sequence":"additional","affiliation":[]},{"given":"Pu","family":"Gao","sequence":"additional","affiliation":[]},{"given":"No\u00ebla","family":"M\u00fcller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,4]]},"reference":[{"key":"3897_CR1","first-page":"721","volume-title":"Proc. 12th SODA","author":"D Achlioptas","year":"2001","unstructured":"D. Achlioptas, A. Chtcherba, G. Istrate and C. Moore: The phase transition in 1-in-k SAT and NAE 3-SAT, Proc. 12th SODA (2001), 721\u2013722."},{"key":"3897_CR2","first-page":"793","volume-title":"Proc. 49th FOCS","author":"D Achlioptas","year":"2008","unstructured":"D. Achlioptas and A. Coja-oghlan: Algorithmic barriers from phase transitions, Proc. 49th FOCS (2008), 793\u2013802."},{"key":"3897_CR3","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1002\/rsa.20494","volume":"46","author":"D Achlioptas","year":"2015","unstructured":"D. Achlioptas and M. Molloy: The solution space geometry of random linear equations, Random Structures and Algorithms46 (2015), 197\u2013231.","journal-title":"Random Structures and Algorithms"},{"key":"3897_CR4","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/S0097539703434231","volume":"36","author":"D Achlioptas","year":"2006","unstructured":"D. Achlioptas and C. Moore: Random fc-SAT: two moments suffice to cross a sharp threshold, SIAM Journal on Computing36 (2006), 740\u2013762.","journal-title":"SIAM Journal on Computing"},{"key":"3897_CR5","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.4007\/annals.2005.162.1335","volume":"162","author":"D Achlioptas","year":"2005","unstructured":"D. Achlioptas and A. Naor: The two possible values of the chromatic number of a random graph, Annals of Mathematics162 (2005), 1333\u20131349.","journal-title":"Annals of Mathematics"},{"key":"3897_CR6","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1038\/nature03602","volume":"435","author":"D Achlioptas","year":"2005","unstructured":"D. Achlioptas, A. Naor and Y. Peres: Rigorous location of phase transitions in hard optimization problems, Nature435 (2005), 759\u2013764.","journal-title":"Nature"},{"key":"3897_CR7","doi-asserted-by":"crossref","unstructured":"M. Alzenman, R. Sims and S. Starr: An extended variational principle for the SK spin-glass model, Phys. Rev. B68 (2003), 214403.","DOI":"10.1103\/PhysRevB.68.214403"},{"key":"3897_CR8","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1002\/rsa.20692","volume":"49","author":"V Bapst","year":"2016","unstructured":"V. Bapst and A. Coja-Oghlan: Harnessing the Bethe free energy, Random Structures and Algorithms49 (2016), 694\u2013741.","journal-title":"Random Structures and Algorithms"},{"key":"3897_CR9","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"B-S E","year":"2001","unstructured":"E. Ben-Spasson and A. Wlgderson: Short proofs are narrow-resolution made simple, Journal of the ACM48 (2001), 149\u2013169.","journal-title":"Journal of the ACM"},{"key":"3897_CR10","first-page":"331","volume-title":"Proc. IJCAI","author":"C P","year":"1991","unstructured":"P. Cheeseman, B. Kanefsky and W. Taylor: Where the really hard problems are, Proc. IJCAI (1991), 331\u2013337."},{"key":"3897_CR11","first-page":"620","volume-title":"Proc. 33th FOCS","author":"V Chv\u00e1tal","year":"1992","unstructured":"V. Chv\u00e1tal and B. Reed: Mick gets some (the odds are on his side), Proc. 33th FOCS (1992), 620\u2013627."},{"key":"3897_CR12","doi-asserted-by":"crossref","first-page":"047205","DOI":"10.1103\/PhysRevLett.90.047205","volume":"90","author":"S Cocco","year":"2003","unstructured":"S. Cocco, O. Dubois, J. Mandler and R. Monasson: Rigorous decimation-based construction of ground pure states for spin glass models on random lattices, Phys. Rev. Lett.90 (2003), 047205.","journal-title":"Phys. Rev. Lett."},{"key":"3897_CR13","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1007\/s00220-018-3096-x","volume":"359","author":"A Coja-oghlan","year":"2018","unstructured":"A. Coja-oghlan, C. Efthymiou, N. Jaafari, M. Kang and T. Kapetanopou- LOS: Charting the replica symmetric phase, Communications in Mathematical Physics359 (2018), 603\u2013698.","journal-title":"Communications in Mathematical Physics"},{"key":"3897_CR14","first-page":"146","volume-title":"Proc. 48th STOC","author":"A Coja-oghlan","year":"2017","unstructured":"A. Coja-oghlan, F. Krzakala, W. Perkins and L. Zdeborova: Information-theoretic thresholds from the cavity method, Proc. 48th STOC (2017), 146\u2013157."},{"key":"3897_CR15","first-page":"985","volume":"288","author":"A Coja-OGHLAN","year":"2016","unstructured":"A. Coja-OGHLAN and K. Panagiotou: The asymptotic k-SAT threshold, Advances in Mathematics288 (2016), 985\u20131068.","journal-title":"in Mathematics"},{"key":"3897_CR16","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1137\/090777268","volume":"26","author":"H Connamacher","year":"2012","unstructured":"H. Connamacher and M. Molloy: The satisfiability threshold for a seemingly intractable random constraint satisfaction problem, SIAM J. DISCRETE Mathematics26 (2012), 768\u2013800.","journal-title":"SIAM J. DISCRETE Mathematics"},{"key":"3897_CR17","first-page":"946","volume-title":"Proc. 30th SODA","author":"C Cooper","year":"2019","unstructured":"C. Cooper, A. Frieze and W. Pegden: On the rank of a random binary matrix, Proc. 30th SODA (2019), 946\u2013955."},{"key":"3897_CR18","first-page":"213","volume-title":"Proc. 37th ICALP","author":"M Dietzfelbinger","year":"2010","unstructured":"M. Dietzfelbinger, A. Goerdt, M. Mltzenmacher, A. Montanari, R. Pagh and M. Rink: Tight thresholds for cuckoo hashing via XORSAT, Proc. 37th ICALP (2010), 213\u2013225."},{"key":"3897_CR19","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/s00220-015-2492-8","volume":"341","author":"J Ding","year":"2016","unstructured":"J. Ding, A. Sly and N. Sun: Satisfiability threshold for random regular NAE-SAT, Communications in Mathematical Physics341 (2016), 435\u2013489.","journal-title":"Communications in Mathematical Physics"},{"key":"3897_CR20","first-page":"59","volume-title":"Proc. 47th STOC","author":"J Ding","year":"2015","unstructured":"J. Ding, A. Sly and N. Sun: Proof of the satisfiability conjecture for large k, Proc. 47th STOC (2015), 59\u201368."},{"key":"3897_CR21","first-page":"769","volume-title":"Proc. 43rd FOCS","author":"O Dubois","year":"2002","unstructured":"O. Dubois and J. Mandler: The 3-XORSAT threshold, Proc. 43rd FOCS (2002), 769\u2013778."},{"key":"3897_CR22","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.jctb.2015.01.002","volume":"113","author":"M Dyer","year":"2015","unstructured":"M. Dyer, A. Frieze and C. Greenhill: On the chromatic number of a random hypergraph, J. Comb. Theory Series B113 (2015), 68\u2013122.","journal-title":"J. Comb. Theory Series B"},{"key":"3897_CR23","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"P. Erd\u0151s and A. Renyi: On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutato Int. K\u00f6zl.5 (1960), 17\u201361.","journal-title":"Magyar Tud. Akad. Mat. Kutato Int. K\u00f6zl."},{"key":"3897_CR24","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s00493-005-0017-3","volume":"25","author":"A Frieze","year":"2005","unstructured":"A. Frieze and N. Wormald: Random k-Sat: a tight threshold for moderately growing k, Combinatorica25 (2005), 297\u2013305.","journal-title":"Combinatorica"},{"key":"3897_CR25","first-page":"50","volume":"62","author":"A Galanis","year":"2015","unstructured":"A. Galanis, D. Stefankovic and E. Vlgoda: Inapproximability for antiferromag-netic spin systems in the tree nonuniqueness region, J. A CM62 (2015), 50.","journal-title":"J. A CM"},{"key":"3897_CR26","unstructured":"P. Gao and M. Molloy: The stripping process can be slow: part I, arXiv:1501.02695 (2015)."},{"key":"3897_CR27","first-page":"264","volume-title":"Proc. 17th MFCS","author":"A Goerdt","year":"1992","unstructured":"A. Goerdt: A threshold for unsatisfiability, Proc. 17th MFCS (1992), 264\u2013274."},{"key":"3897_CR28","first-page":"148","volume-title":"Proc. 7th International Computer Science Symposium in Russia","author":"A Goerdt","year":"2012","unstructured":"A. Goerdt and L. Falke: Satisfiability thresholds beyond k-XORSAT, Proc. 7th International Computer Science Symposium in Russia (2012), 148\u2013159."},{"key":"3897_CR29","doi-asserted-by":"crossref","first-page":"2743","DOI":"10.1214\/14-AAP1060","volume":"25","author":"M Ibrahimi","year":"2015","unstructured":"M. Ibrahimi, Y. Kanoria, M. Kraning and A. Montanari: The set of solutions of random XORSAT formulae, Annals of Applied Probability25 (2015), 2743\u20132808.","journal-title":"Annals of Applied Probability"},{"key":"3897_CR30","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1209\/epl\/i1999-00137-2","volume":"45","author":"Y Kabashima","year":"1999","unstructured":"Y. Kabashima and D. Saad: Statistical mechanics of error correcting codes, Euro-phys. Lett.45 (1999), 97\u2013103.","journal-title":"Euro-phys. Lett."},{"key":"3897_CR31","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S Klrkpatrick","year":"1994","unstructured":"S. Klrkpatrick and B. Selman: Critical behavior in the satisfiability of random Boolean expressions, Science264 (1994), 1297\u20131301.","journal-title":"Science"},{"key":"3897_CR32","first-page":"425","volume":"5","author":"V Kolchin","year":"1995","unstructured":"V. Kolchin: Random graphs and systems of linear equations in finite fields, Random Structures and Algorithms5 (1995), 425\u2013436.","journal-title":"Random Structures and Algorithms"},{"key":"3897_CR33","doi-asserted-by":"crossref","first-page":"10318","DOI":"10.1073\/pnas.0703685104","volume":"104","author":"F Krzakala","year":"2007","unstructured":"F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zde-Borov\u00e1: Gibbs states and the set of solutions of random constraint satisfaction problems, Proc. National Academy of Sciences104 (2007), 10318\u201310323.","journal-title":"Proc. National Academy of Sciences"},{"key":"3897_CR34","first-page":"494","volume-title":"Proc. ALLERTON","author":"R Mceliece","year":"1996","unstructured":"R. Mceliece and J. Cheng: Some high-rate near capacity codecs for the Gaussian channel, Proc. ALLERTON (1996), 494\u2013503."},{"key":"3897_CR35","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, physics and computation","author":"M Mezard","year":"2009","unstructured":"M. Mezard and A. Montanari: Information, physics and computation, Oxford University Press 2009."},{"key":"3897_CR36","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M Mezard","year":"2002","unstructured":"M. Mezard, G. Parisi and R. Zecchina: Analytic and algorithmic solution of random satisfiability problems, Science297 (2002), 812\u2013815.","journal-title":"Science"},{"key":"3897_CR37","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1023\/A:1022886412117","volume":"111","author":"M Mezard","year":"2003","unstructured":"M. Mezard, F. Ricci-Tersenghi and R. Zecchina: TWO solutions to diluted p-spin models and XORSAT problems, Journal of Statistical Physics111 (2003), 505\u2013533.","journal-title":"Journal of Statistical Physics"},{"key":"3897_CR38","first-page":"459","volume-title":"Proc. 10th AAAI","author":"D Mitchell","year":"1992","unstructured":"D. Mitchell, B. Selman and H. Levesque: Hard and easy distribution of SAT problems, Proc. 10th AAAI (1992), 459\u2013465."},{"key":"3897_CR39","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1002\/rsa.20061","volume":"27","author":"M Molloy","year":"2005","unstructured":"M. Molloy: Cores in random hypergraphs and Boolean formulas, Random Structures and Algorithms27 (2005), 124\u2013135.","journal-title":"Random Structures and Algorithms"},{"key":"3897_CR40","doi-asserted-by":"crossref","first-page":"349","DOI":"10.4171\/AIHPD\/31","volume":"3","author":"C Moore","year":"2016","unstructured":"C. Moore: The phase transition in random regular exact cover, Annales l\u2019institut Henri Poincare D, combinatorics, physics and their Interactions3 (2016), 349\u2013362.","journal-title":"Annales l\u2019institut Henri Poincare D, combinatorics, physics and their Interactions"},{"key":"3897_CR41","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1002\/ett.1289","volume":"19","author":"A Montanari","year":"2008","unstructured":"A. Montanari: Estimating random variables from random sparse observations, European Transactions on Telecommunications19 (2008), 385\u2013403.","journal-title":"European Transactions on Telecommunications"},{"key":"3897_CR42","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1017\/S0963548315000097","volume":"25","author":"B Pittel","year":"2016","unstructured":"B. Pittel and G. Sorkin: The satisfiability threshold for k-XORSAT, Combinatorics, Probability and Computing25 (2016), 236\u2013268.","journal-title":"Combinatorics, Probability and Computing"},{"key":"3897_CR43","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511791338","volume-title":"Modern coding theory","author":"T Richardson","year":"2008","unstructured":"T. Richardson and R. Urbanke: Modern coding theory, Cambridge University Press (2008)."},{"key":"3897_CR44","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1002\/rsa.3240030202","volume":"3","author":"R Robinson","year":"1992","unstructured":"R. Robinson and N. Wormald: Almost all cubic graphs are Hamiltonian, Random Structures and Algorithms3 (1992), 117\u2013125.","journal-title":"Random Structures and Algorithms"},{"key":"3897_CR45","first-page":"287","volume-title":"Proc. 51st FOCS","author":"A Sly","year":"2010","unstructured":"A. Sly: Computational transition at the uniqueness threshold, Proc. 51st FOCS (2010), 287\u2013296."},{"key":"3897_CR46","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L Valiant","year":"1986","unstructured":"L. Valiant and V. Vazirani: NP is as easy as detecting unique solutions, Theoretical Computer Science47 (1986), 85\u201393.","journal-title":"Theoretical Computer Science"},{"key":"3897_CR47","doi-asserted-by":"crossref","first-page":"1351","DOI":"10.1109\/TIT.2009.2039160","volume":"56","author":"M J Wainwright","year":"2010","unstructured":"M. J. Wainwright, E. Maneva and E. Martinian: Lossy source compression using low-density generator matrix codes: Analysis and algorithms, IEEE Transactions on Information theory56 (2010), 1351\u20131368.","journal-title":"IEEE Transactions on Information theory"},{"key":"3897_CR48","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1080\/00018732.2016.1211393","volume":"65","author":"L Zdeborov\u00e1","year":"2016","unstructured":"L. Zdeborov\u00e1 and F. Krzakala: Statistical physics of inference: thresholds and algorithms, Advances in Physics65 (2016), 453\u2013552.","journal-title":"Advances in Physics"},{"key":"3897_CR49","doi-asserted-by":"crossref","first-page":"078702","DOI":"10.1103\/PhysRevLett.101.078702","volume":"101","author":"L Zdeborov\u00e1","year":"2008","unstructured":"L. Zdeborov\u00e1 and M. M\u00e9zard: Locked constraint satisfaction problems, Phys. Rev. Lett.101 (2008), 078702.","journal-title":"Phys. Rev. Lett."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-3897-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-019-3897-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-3897-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T00:50:29Z","timestamp":1614819029000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-019-3897-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,4]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["3897"],"URL":"https:\/\/doi.org\/10.1007\/s00493-019-3897-3","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,4]]},"assertion":[{"value":"7 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}