{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T03:11:23Z","timestamp":1772507483969,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,5,19]]},"DOI":"10.1145\/2213977.2214058","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"899-908","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Catching the k-NAESAT threshold"],"prefix":"10.1145","author":[{"given":"Amin","family":"Coja-Oglan","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}]},{"given":"Konstantinos","family":"Panagiotou","sequence":"additional","affiliation":[{"name":"University of Munich, M\u00fcnchen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.997.abs"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434231"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1335"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03602"},{"key":"e_1_3_2_2_6_1","first-page":"947","volume":"17","author":"Achlioptas D.","year":"2004","unstructured":"D. Achlioptas , Y. Peres:The threshold for random k-SAT is 2k ln 2 - O(k). Journal of the AMS 17 ( 2004 ) 947 -- 973 . D. Achlioptas, Y. Peres:The threshold for random k-SAT is 2k ln 2 - O(k). Journal of the AMS 17 (2004) 947--973.","journal-title":"Journal of the AMS"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132537"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267789"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076516X"},{"key":"e_1_3_2_2_10_1","volume-title":"Efthymiou: On independent sets in random graphs.Proc. 22nd SODA (2011) 136--144","author":"Coja-Oghlan A.","unstructured":"A. Coja-Oghlan , C. Efthymiou: On independent sets in random graphs.Proc. 22nd SODA (2011) 136--144 . A. Coja-Oghlan, C. Efthymiou: On independent sets in random graphs.Proc. 22nd SODA (2011) 136--144."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.37236\/877"},{"key":"e_1_3_2_2_12_1","volume-title":"to appear","author":"Coja-Oghlan A.","year":"2012","unstructured":"A. Coja-Oghlan , L. Zdeborov\u00e1:The condensation transition in random hypergraph 2-coloring. Proc . 23rd SODA ( 2012 ), to appear . A. Coja-Oghlan, L. Zdeborov\u00e1:The condensation transition in random hypergraph 2-coloring.Proc. 23rd SODA (2012), to appear."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.66"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.77.031118"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.005"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0867"},{"key":"e_1_3_2_2_17_1","volume-title":"Proc. 43rd FOCS (2002)","author":"Dubois O.","unstructured":"O. Dubois , J. Mandler : The 3-XORSAT threshold . Proc. 43rd FOCS (2002) 769--778. O. Dubois, J. Mandler: The 3-XORSAT threshold. Proc. 43rd FOCS (2002) 769--778."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095141"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_32"},{"key":"e_1_3_2_2_20_1","volume-title":"Cambridge","author":"Flajolet P.","year":"2009","unstructured":"P. Flajolet , R. Sedgewick: Analyitic Combinatorics . Cambridge University Press , Cambridge , 2009 . P. Flajolet, R. Sedgewick:Analyitic Combinatorics.Cambridge University Press, Cambridge, 2009."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022885828956"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v26:1\/2"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0017-3"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.58"},{"key":"e_1_3_2_2_25_1","volume-title":"Proc. 17th MFCS (1992)","author":"Goerdt A.","unstructured":"A. Goerdt : A threshold for unsatisfiability . Proc. 17th MFCS (1992) 264--274. A. Goerdt: A threshold for unsatisfiability. Proc. 17th MFCS (1992) 264--274."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199805)12:3%3C253::AID-RSA3%3E3.0.CO;2-U"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v28:3"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/090755862"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-008-9543-x"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0342-2"},{"key":"e_1_3_2_2_33_1","unstructured":"B. Pittel G. Sorkin:The satisfiability threshold for k-XORSAT. Preprint (2011).  B. Pittel G. Sorkin:The satisfiability threshold for k-XORSAT. Preprint (2011)."}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214058","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2214058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2214058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":33,"alternative-id":["10.1145\/2213977.2214058","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2214058","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}