{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:25Z","timestamp":1759638265706,"version":"3.28.0"},"reference-count":34,"publisher":"IEEE","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1109\/focs.2012.71","type":"proceedings-article","created":{"date-parts":[[2012,12,12]],"date-time":"2012-12-12T22:01:38Z","timestamp":1355349698000},"page":"609-618","source":"Crossref","is-referenced-by-count":36,"title":["New Limits to Classical and Quantum Instance Compression"],"prefix":"10.1109","author":[{"given":"Andrew","family":"Drucker","sequence":"first","affiliation":[]}],"member":"263","reference":[{"key":"19","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049704"},{"journal-title":"Quantum Computation and Quantum Information","year":"2000","author":"nielsen","key":"17"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00375-9"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1664"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/2635808"},{"key":"34","first-page":"4","article-title":"On the complexity of computational problems regarding distributions (a survey)","volume":"tr11 4","author":"goldreich","year":"2011","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.21"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.9"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.6"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22006-7_37"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9270-y"},{"journal-title":"Entropy-based Bounds on Dimension Reduction in L1","year":"2011","author":"regev","key":"21"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636868"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.811927"},{"key":"23","article-title":"Generalised pinsker inequalities","author":"reid","year":"2009","journal-title":"COLT"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.896888"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195447"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(94)90357-3"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814608"},{"journal-title":"Elements of Information Theory","year":"2006","author":"cover","key":"29"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"10","first-page":"145","article-title":"Kernel bounds for path and cycle problems","author":"bodlaender","year":"2011","journal-title":"IPEC"},{"key":"1","article-title":"Parametrized Complexity","author":"downey","year":"1999","journal-title":"Monographs in Computer Science"},{"key":"30","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.37"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"6","first-page":"165","article-title":"Cross-composition: A new technique for kernelization lower bounds","author":"bodlaender","year":"2011","journal-title":"STACS"},{"key":"32","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90006-Q"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"31","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28418"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"}],"event":{"name":"2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)","start":{"date-parts":[[2012,10,20]]},"location":"New Brunswick, NJ, USA","end":{"date-parts":[[2012,10,23]]}},"container-title":["2012 IEEE 53rd Annual Symposium on Foundations of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/6374356\/6375275\/06375340.pdf?arnumber=6375340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,3,21]],"date-time":"2017-03-21T21:12:06Z","timestamp":1490130726000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/6375340\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":34,"URL":"https:\/\/doi.org\/10.1109\/focs.2012.71","relation":{},"subject":[],"published":{"date-parts":[[2012,10]]}}}