{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T04:16:14Z","timestamp":1780719374873,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"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":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806725","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"251-260","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":66,"title":["Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses"],"prefix":"10.1145","author":[{"given":"Holger","family":"Dell","sequence":"first","affiliation":[{"name":"Humboldt University of Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"van Melkebeek","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434231"},{"issue":"4","key":"e_1_3_2_1_2_1","first-page":"947","article-title":"The threshold for random k-SAT is 2k log 2-O(k)","volume":"17","author":"Achlioptas D.","year":"2004","unstructured":"D. Achlioptas and Y. Peres . The threshold for random k-SAT is 2k log 2-O(k) . Journal of the AMS , 17 ( 4 ): 947 -- 973 , 2004 . D. Achlioptas and Y. Peres. The threshold for random k-SAT is 2k log 2-O(k). Journal of the AMS, 17(4):947--973, 2004.","journal-title":"Journal of the AMS"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/07067917X"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.008"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a009"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007759"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_57"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222038"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_3_2_1_14_1","volume-title":"Lower bounds for kernelizations. ECCC, 14(137)","author":"Chen Y.","year":"2007","unstructured":"Y. Chen , J. Flum , and M. Muller . Lower bounds for kernelizations. ECCC, 14(137) , 2007 . Y. Chen, J. Flum, and M. Muller. Lower bounds for kernelizations. ECCC, 14(137), 2007."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_1_17_1","volume-title":"Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. ECCC, 17(38)","author":"Dell H.","year":"2010","unstructured":"H. Dell and D. van Melkebeek . Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. ECCC, 17(38) , 2010 . H. Dell and D. van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. ECCC, 17(38), 2010."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"e_1_3_2_1_21_1","first-page":"409","volume-title":"STACS","author":"Fellows M. R.","year":"2009","unstructured":"M. R. Fellows , J. Guo , H. Moser , and R. Niedermeier . A generalization of Nemhauser and Trotter's local optimization theorem . In STACS , pages 409 -- 420 , 2009 . M. R. Fellows, J. Guo, H. Moser, and R. Niedermeier. A generalization of Nemhauser and Trotter's local optimization theorem. In STACS, pages 409--420, 2009."},{"key":"e_1_3_2_1_22_1","first-page":"421","volume-title":"STACS","author":"Fernau H.","year":"2009","unstructured":"H. Fernau , F. V. Fomin , D. Lokshtanov , D. Raible , S. Saurabh , and Y. Villanger . Kernel(s) for problems with no kernel: On out-trees with many leaves . In STACS , pages 421 -- 432 , 2009 . H. Fernau, F. V. Fomin, D. Lokshtanov, D. Raible, S. Saurabh, and Y. Villanger. Kernel(s) for problems with no kernel: On out-trees with many leaves. In STACS, pages 421--432, 2009."},{"key":"e_1_3_2_1_23_1","volume-title":"Parameterized Complexity Theory","author":"Flum J.","year":"2006","unstructured":"J. Flum and M. Grohe . Parameterized Complexity Theory . Springer , 2006 . J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374398"},{"issue":"4","key":"e_1_3_2_1_25_1","first-page":"1017","article-title":"Sharp thresholds of graph properties, and the k-SAT problem","volume":"12","author":"Friedgut E.","year":"1999","unstructured":"E. Friedgut and J. Bourgain . Sharp thresholds of graph properties, and the k-SAT problem . Journal of the AMS , 12 ( 4 ): 1017 -- 1054 , 1999 . E. Friedgut and J. Bourgain. Sharp thresholds of graph properties, and the k-SAT problem. Journal of the AMS, 12(4):1017--1054, 1999.","journal-title":"Journal of the AMS"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.54"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_31_1","volume-title":"Complexity of computer computations, 43:85--103","author":"Karp R. M.","year":"1972","unstructured":"R. M. Karp . Reducibility among combinatorial problems. Complexity of computer computations, 43:85--103 , 1972 . R. M. Karp. Reducibility among combinatorial problems. Complexity of computer computations, 43:85--103, 1972."},{"key":"e_1_3_2_1_32_1","volume-title":"Arxiv Preprint","author":"Kratsch S.","year":"2009","unstructured":"S. Kratsch and M. Wahlstrom . Preprocessing of min ones problems: A dichotomy . Arxiv Preprint , 2009 . S. Kratsch and M. Wahlstrom. Preprocessing of min ones problems: A dichotomy. Arxiv Preprint, 2009."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_22"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208049"},{"issue":"3","key":"e_1_3_2_1_35_1","first-page":"265","article-title":"Universal search problems","volume":"9","author":"Levin L. A.","year":"1973","unstructured":"L. A. Levin . Universal search problems . Problemy Peredachi Informatsii , 9 ( 3 ): 265 -- 266 , 1973 . L. A. Levin. Universal search problems. Problemy Peredachi Informatsii, 9(3):265--266, 1973.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_3_2_1_37_1","series-title":"Colloquia Mathematica Societatis Janos Bolyai","first-page":"939","volume-title":"Combinatorics","author":"Ruzsa I. Z.","year":"1978","unstructured":"I. Z. Ruzsa and E. Szemeredi . Triple systems with no six points carrying three triangles . In Combinatorics , Vol. II, volume 18 of Colloquia Mathematica Societatis Janos Bolyai , pages 939 -- 945 . North-Holland , 1978 . I. Z. Ruzsa and E. Szemeredi. Triple systems with no six points carrying three triangles. In Combinatorics, Vol. II, volume 18 of Colloquia Mathematica Societatis Janos Bolyai, pages 939--945. North-Holland, 1978."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.28.12.561"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496783"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90020-8"}],"event":{"name":"STOC'10: Symposium on Theory of Computing","location":"Cambridge Massachusetts USA","acronym":"STOC'10","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806725","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":40,"alternative-id":["10.1145\/1806689.1806725","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806725","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}