{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:10Z","timestamp":1784568310163,"version":"3.55.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0728809, CCF-1017597, CCF-1319822"],"award-info":[{"award-number":["CCF-0728809, CCF-1017597, CCF-1319822"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>\n            Consider the following two-player communication process to decide a language\n            <jats:italic>L<\/jats:italic>\n            : The first player holds the entire input\n            <jats:italic>x<\/jats:italic>\n            but is polynomially bounded; the second player is computationally unbounded but does not know any part of\n            <jats:italic>x<\/jats:italic>\n            ; their goal is to decide cooperatively whether\n            <jats:italic>x<\/jats:italic>\n            belongs to\n            <jats:italic>L<\/jats:italic>\n            at small cost, where the cost measure is the number of bits of communication from the first player to the second player.\n          <\/jats:p>\n          <jats:p>\n            For any integer\n            <jats:italic>d<\/jats:italic>\n            \u2009\u2265\u20093 and positive real\n            <jats:italic>\u03b5<\/jats:italic>\n            , we show that, if satisfiability for\n            <jats:italic>n<\/jats:italic>\n            -variable\n            <jats:italic>d<\/jats:italic>\n            -CNF formulas has a protocol of cost\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nd<\/jats:italic>\n            \u2009\u2212\u2009\n            <jats:italic>\u03b5<\/jats:italic>\n            ), then coNP is in NP\/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for\n            <jats:italic>\u03b5<\/jats:italic>\n            \u2009=\u20090. Under the hypothesis that coNP is not in NP\/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs.\n          <\/jats:p>\n          <jats:p>\n            By reduction, similar results hold for other NP-complete problems. For the vertex cover problem on\n            <jats:italic>n<\/jats:italic>\n            -vertex\n            <jats:italic>d<\/jats:italic>\n            -uniform hypergraphs, this statement holds for any integer\n            <jats:italic>d<\/jats:italic>\n            \u2009\u2265\u20092. The case\n            <jats:italic>d<\/jats:italic>\n            \u2009=\u20092 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            2\u2009\u2212\u2009\n            <jats:italic>\u03b5<\/jats:italic>\n            ) edges unless coNP is in NP\/poly, where\n            <jats:italic>k<\/jats:italic>\n            denotes the size of the deletion set. Kernels consisting of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.\n          <\/jats:p>","DOI":"10.1145\/2629620","type":"journal-article","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T13:53:48Z","timestamp":1407851628000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":106,"title":["Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses"],"prefix":"10.1145","volume":"61","author":[{"given":"Holger","family":"Dell","sequence":"first","affiliation":[{"name":"LIAFA, Universit\u00e9 Paris Diderot, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"Van Melkebeek","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434231"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-04-00464-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/07067917X"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a009"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007759"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344428"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309009821"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.21"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222038"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2160-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9270-y"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0308210511001648"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Dell H.","unstructured":"Dell , H. and Marx , D . 2012. Kernelization of packing problems . In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912) . SIAM, 68--81. Dell, H. and Marx, D. 2012. Kernelization of packing problems. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912). SIAM, 68--81."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer New York.   Downey R. G. and Fellows M. R. 1999. Parameterized Complexity . Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.71"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008644"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.12.001"},{"key":"e_1_2_1_31_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory . Springer."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1373317"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68361-4_9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054195000214"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90013-2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095126"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Kratsch S.","unstructured":"Kratsch , S. , Philip , G. , and Ray , S . 2014. Point line cover: The easy kernel is essentially tight . In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914) . SIAM, 1596--1606. Kratsch, S., Philip, G., and Ray, S. 2014. Point line cover: The easy kernel is essentially tight. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). SIAM, 1596--1606."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880989"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Kratsch S. and Wahlstr\u00f6m M. 2013. Two edge modification problems without polynomial kernels. Disc. Optim.  Kratsch S. and Wahlstr\u00f6m M. 2013. Two edge modification problems without polynomial kernels. Disc. Optim.","DOI":"10.1016\/j.disopt.2013.02.001"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208049"},{"key":"e_1_2_1_49_1","first-page":"265","article-title":"Universal search problems (Russian: Universal\u2019nye perebornye zadachi)","volume":"9","author":"Levin L. A.","year":"1973","unstructured":"Levin , L. A. 1973 . Universal search problems (Russian: Universal\u2019nye perebornye zadachi) . Prob. Inf. Trans. (Russian: Problemy Peredachi Informatsii) 9 , 3, 265 -- 266 . Levin, L. A. 1973. Universal search problems (Russian: Universal\u2019nye perebornye zadachi). Prob. Inf. Trans. (Russian: Problemy Peredachi Informatsii) 9, 3, 265--266.","journal-title":"Prob. Inf. Trans. (Russian: Problemy Peredachi Informatsii)"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_51_1","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier R.","unstructured":"Niedermeier , R. 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press , Oxford, UK . Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford, UK."},{"key":"e_1_2_1_52_1","volume-title":"Combinatorics (Proceedings of the 5th Hungarian Colloquium, Keszthely","author":"Ruzsa I. Z.","year":"1976","unstructured":"Ruzsa , I. Z. and Szemer\u00e9di , E . 1978. Triple systems with no six points carrying three triangles . In Combinatorics (Proceedings of the 5th Hungarian Colloquium, Keszthely , 1976 ), Vol. II , Colloquia Mathematica Societatis J\u00e1nos Bolyai , vol. 18, North-Holland, Amsterdam, 939--945. Ruzsa, I. Z. and Szemer\u00e9di, E. 1978. Triple systems with no six points carrying three triangles. In Combinatorics (Proceedings of the 5th Hungarian Colloquium, Keszthely, 1976), Vol. II, Colloquia Mathematica Societatis J\u00e1nos Bolyai, vol. 18, North-Holland, Amsterdam, 939--945."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.28.12.561"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721848"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Wegener I. 1987. The Complexity of Boolean Functions. B. G. Teubner and John Wiley & Sons.   Wegener I. 1987. The Complexity of Boolean Functions . B. G. Teubner and John Wiley & Sons.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90020-8"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629620","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629620","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:29Z","timestamp":1750227209000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629620"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2629620"],"URL":"https:\/\/doi.org\/10.1145\/2629620","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7]]},"assertion":[{"value":"2010-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}