{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:36:53Z","timestamp":1770903413402,"version":"3.50.1"},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2015,7,31]],"date-time":"2015-07-31T00:00:00Z","timestamp":1438300800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2016,3]]},"abstract":"<jats:p>We consider \u2018unconstrained\u2019 random<jats:italic>k<\/jats:italic>-XORSAT, which is a uniformly random system of<jats:italic>m<\/jats:italic>linear non-homogeneous equations in<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548315000097_inline1\"\/><jats:tex-math>$\\mathbb{F}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula><jats:sub>2<\/jats:sub>over<jats:italic>n<\/jats:italic>variables, each equation containing<jats:italic>k<\/jats:italic>\u2a7e 3 variables, and also consider a \u2018constrained\u2019 model where every variable appears in at least two equations. Dubois and Mandler proved that<jats:italic>m\/n<\/jats:italic>= 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.<\/jats:p><jats:p>We show that<jats:italic>m\/n<\/jats:italic>= 1 remains a sharp threshold for satisfiability of constrained<jats:italic>k<\/jats:italic>-XORSAT for every<jats:italic>k<\/jats:italic>\u2a7e 3, and we use standard results on the 2-core of a random<jats:italic>k<\/jats:italic>-uniform hypergraph to extend this result to find the threshold for unconstrained<jats:italic>k<\/jats:italic>-XORSAT. For constrained<jats:italic>k<\/jats:italic>-XORSAT we narrow the phase transition window, showing that<jats:italic>m \u2212 n<\/jats:italic>\u2192 \u2212\u221e implies almost-sure satisfiability, while<jats:italic>m \u2212 n<\/jats:italic>\u2192 +\u221e implies almost-sure unsatisfiability.<\/jats:p>","DOI":"10.1017\/s0963548315000097","type":"journal-article","created":{"date-parts":[[2015,7,31]],"date-time":"2015-07-31T03:36:32Z","timestamp":1438313792000},"page":"236-268","source":"Crossref","is-referenced-by-count":26,"title":["The Satisfiability Threshold for<i>k<\/i>-XORSAT"],"prefix":"10.1017","volume":"25","author":[{"given":"BORIS","family":"PITTEL","sequence":"first","affiliation":[]},{"given":"GREGORY B.","family":"SORKIN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2015,7,31]]},"reference":[{"key":"S0963548315000097_ref30","doi-asserted-by":"crossref","first-page":"R92","DOI":"10.37236\/364","article-title":"How frequently is a system of 2-linear equations solvable?","volume":"17","author":"Pittel","year":"2010","journal-title":"Electron. J. Combin."},{"key":"S0963548315000097_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#"},{"key":"S0963548315000097_ref18","unstructured":"Fernandez de la Vega W. (1992) On random 2-SAT. Manuscript."},{"key":"S0963548315000097_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20040"},{"key":"S0963548315000097_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1006"},{"key":"S0963548315000097_ref19","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"S0963548315000097_ref22","volume-title":"Encyclopedia of Mathematics and its Applications","author":"Kolchin","year":"1999"},{"key":"S0963548315000097_ref7","unstructured":"Chv\u00e1tal 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\u2013627."},{"key":"S0963548315000097_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<209::AID-RSA6>3.0.CO;2-1"},{"key":"S0963548315000097_ref28","unstructured":"Pittel B. and Sorkin G. B. (2012) The satisfiability threshold for k-XORSAT, using an alternative proof. arXiv:1212.3822"},{"key":"S0963548315000097_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1182002"},{"key":"S0963548315000097_ref15","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger M. , Goerdt A. , Mitzenmacher M. , Montanari A. , Pagh R. and Rink M. (2010) Tight thresholds for cuckoo hashing via XORSAT. arXiv:0912.0287v3","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"S0963548315000097_ref20","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0081"},{"key":"S0963548315000097_ref11","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2003014"},{"key":"S0963548315000097_ref12","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v19-2458"},{"key":"S0963548315000097_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/S0001867800015603"},{"key":"S0963548315000097_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199707)10:4<407::AID-RSA1>3.0.CO;2-Y"},{"key":"S0963548315000097_ref21","first-page":"873","volume-title":"Eur. Math. Soc.","author":"Kim","year":"2006"},{"key":"S0963548315000097_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78773-0_2"},{"key":"S0963548315000097_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S1631-073X(02)02563-3"},{"key":"S0963548315000097_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20015"},{"key":"S0963548315000097_ref24","unstructured":"M\u00e9zard M. , Ricci-Tersenghi F. and Zecchina R. (2014) Personal communication."},{"key":"S0963548315000097_ref3","unstructured":"Balister P. (2012) Personal communication."},{"key":"S0963548315000097_ref6","volume-title":"Asymptotic Methods in Analysis","author":"de Bruijn","year":"1981"},{"key":"S0963548315000097_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20494"},{"key":"S0963548315000097_ref31","volume-title":"Mathematical Statistical Mechanics","author":"Thompson","year":"1972"},{"key":"S0963548315000097_ref23","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022886412117"},{"key":"S0963548315000097_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"S0963548315000097_ref29","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0036"},{"key":"S0963548315000097_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"S0963548315000097_ref27","unstructured":"Pittel B. and Sorkin G. B. (2012) The satisfiability threshold for k-XORSAT. arXiv:1212.1905v1"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548315000097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,6]],"date-time":"2020-09-06T18:26:17Z","timestamp":1599416777000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548315000097\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,31]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["S0963548315000097"],"URL":"https:\/\/doi.org\/10.1017\/s0963548315000097","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,31]]}}}