{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:07Z","timestamp":1750694707555},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382321"},{"type":"electronic","value":"9783642382338"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38233-8_16","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T12:57:16Z","timestamp":1368622636000},"page":"183-196","source":"Crossref","is-referenced-by-count":2,"title":["Succinct Permanent Is NEXP-Hard with Many Hard Instances"],"prefix":"10.1007","author":[{"given":"Shlomi","family":"Dolev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nova","family":"Fandina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Gutfreund","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","first-page":"781","volume":"2","author":"M. Agrawal","year":"2002","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. of Math\u00a02, 781\u2013793 (2002)","journal-title":"Ann. of Math"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity\u00a01, 3\u201340 (1991)","journal-title":"Computational Complexity"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Computational Complexity\u00a03, 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"key":"16_CR4","first-page":"86","volume":"19","author":"S. Dolev","year":"2012","unstructured":"Dolev, S., Fandina, N., Gutfreund, D.: Succinct Permanent is NEXP-hard with Many Hard Instances. Electronic Colloquium on Computational Complexity (ECCC)\u00a019, 86 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-76627-8_20","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"S. Dolev","year":"2007","unstructured":"Dolev, S., Korach, E., Uzan, G.: Magnifying Computing Gaps Establishing Encrypted Communication over Unidirectional Channels (Extended Abstract). In: Masuzawa, T., Tixeuil, S. (eds.) SSS 2007. LNCS, vol.\u00a04838, pp. 253\u2013265. Springer, Heidelberg (2007)"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1984","unstructured":"Galperin, H., Wigderson, A.: Succinct representations of graphs. Inf. Control\u00a056, 183\u2013198 (1984)","journal-title":"Inf. Control"},{"issue":"4","key":"16_CR7","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/s00037-007-0235-8","volume":"16","author":"D. Gutfreund","year":"2007","unstructured":"Gutfreund, D., Shaltiel, R., Ta-shma, A.: If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances. Computational Complexity\u00a016(4), 412\u2013441 (2007)","journal-title":"Computational Complexity"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1006\/jcss.2001.1780","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Wigderson, A.: Randomness vs time: derandomization under a uniform assumption. J. Comput. Syst. Sci.\u00a063, 672\u2013688 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Lipton, R.: New directions in testing. In: Distributed Computing and Cryptography. DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol.\u00a02, pp. 191\u2013202 (1991)","DOI":"10.1090\/dimacs\/002\/13"},{"issue":"4","key":"16_CR10","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1145\/359460.359473","volume":"21","author":"R.C. Merkle","year":"1978","unstructured":"Merkle, R.C.: Secure Communications Over Insecure Channels. CACM\u00a021(4), 294\u2013299 (1978)","journal-title":"CACM"},{"key":"16_CR11","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C.H. Papadimitriou","year":"1986","unstructured":"Papadimitriou, C.H., Yannakakis, M.: A note on succinct representations of graphs. Inf. Control\u00a071, 181\u2013185 (1986)","journal-title":"Inf. Control"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-540-74510-5_36","volume-title":"Computer Science \u2013 Theory and Applications","author":"A.N. Rybalov","year":"2007","unstructured":"Rybalov, A.N.: Generic Complexity of Presburger Arithmetic. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol.\u00a04649, pp. 356\u2013361. Springer, Heidelberg (2007)"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.P.: Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci.\u00a062, 236\u2013266 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"16_CR15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","volume":"16","author":"L. Trevisan","year":"2007","unstructured":"Trevisan, L., Vadhan, S.: Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity\u00a016(4), 331\u2013364 (2007)","journal-title":"Computational Complexity"},{"issue":"2","key":"16_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38233-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T15:17:12Z","timestamp":1578496632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38233-8_16"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382321","9783642382338"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38233-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}