{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:48:39Z","timestamp":1725889719484},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642332920"},{"type":"electronic","value":"9783642332937"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_13","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T10:50:58Z","timestamp":1346237458000},"page":"120-134","source":"Crossref","is-referenced-by-count":0,"title":["Instance Compression for the Polynomial Hierarchy and beyond"],"prefix":"10.1007","author":[{"given":"Chiranjit","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"13_CR1","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. Journal of the ACM\u00a028(1), 114\u2013133 (1981)","journal-title":"Journal of the ACM"},{"issue":"4","key":"13_CR2","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. Journal of the ACM\u00a039(4), 869\u2013877 (1992)","journal-title":"Journal of the ACM"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.K. Yap","year":"1983","unstructured":"Yap, C.K.: Some consequences of non-uniform conditions on uniform classes. Theoretical Computer Science\u00a026, 287\u2013300 (1983)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"13_CR4","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. Journal of the ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"Journal of the ACM"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 719\u2013728 (2006)","DOI":"10.1109\/FOCS.2006.54"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Hitchcock, J.M.: NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP\/poly. Elect. Colloq. Comput. Complex (ECCC)\u00a015(022) (2008)","DOI":"10.1109\/CCC.2008.21"},{"issue":"8","key":"13_CR7","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR8","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"K.A. Abrahamson","year":"1995","unstructured":"Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of pure and applied logic\u00a073, 235\u2013276 (1995)","journal-title":"Annals of pure and applied logic"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences\u00a036, 254\u2013276 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"13_CR11","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L. Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences\u00a077(1), 91\u2013106 (2011); special issues celebrating Karp\u2019s Kyoto Prize","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR12","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Course Technology, 2nd edn. (2005)"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Lipton, R.J.: Some connections between nonuniform and uniform complexity classes. In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 302\u2013309 (1980), doi:10.1145\/800141.804678","DOI":"10.1145\/800141.804678"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge complexity of interactive proof-systems. In: Proceedings of 17th ACM Symposium on the Theory of Computation, Providence, Rhode Island, pp. 291\u2013304 (1985)","DOI":"10.1145\/22145.22178"},{"key":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/978-3-642-14165-2_55","volume-title":"Automata, Languages and Programming","author":"S. Kratsch","year":"2010","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Preprocessing of Min Ones Problems: A Dichotomy. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 653\u2013665. Springer, Heidelberg (2010)"},{"key":"13_CR18","unstructured":"Chen, Y., Flum, J., Muller, M.: Lower bounds for kernelizations. CRM Publications (November 2008)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:03:21Z","timestamp":1620129801000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}