{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T13:54:45Z","timestamp":1791294885361,"version":"4.1.0"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,12,15]],"date-time":"2013-12-15T00:00:00Z","timestamp":1387065600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s00224-013-9527-3","type":"journal-article","created":{"date-parts":[[2013,12,14]],"date-time":"2013-12-14T06:24:08Z","timestamp":1387002248000},"page":"281-298","source":"Crossref","is-referenced-by-count":11,"title":["The Equivalence of Sampling and Searching"],"prefix":"10.1007","volume":"55","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,12,15]]},"reference":[{"key":"9527_CR1","doi-asserted-by":"crossref","first-page":"143","DOI":"10.4086\/toc.2013.v009a004","volume":"9","author":"S. Aaronson","year":"2013","unstructured":"Aaronson, S., Arkhipov, A.: The computational complexity of linear optics. Theory Comput. 9, 143\u2013252 (2013). Conference version in Proceedings of ACM STOC\u20192011. ECCC TR10-170. arXiv:1011.3245","journal-title":"Theory Comput."},{"key":"9527_CR2","unstructured":"Barak, B.: Non-black-box techniques in cryptography. Ph.D. thesis, Weizmann Institute of Science (2003). www.wisdom.weizmann.ac.il\/~oded\/PS\/boaz-phd.ps"},{"issue":"2","key":"9527_CR3","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1145\/1461928.1461951","volume":"52","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. Commun. ACM 52(2), 89\u201397 (2009). Earlier version in Proceedings of STOC\u20192006","journal-title":"Commun. ACM"},{"key":"9527_CR4","unstructured":"G\u00e1cs, P.: Lecture notes on descriptional complexity and randomness (2010). www.cs.bu.edu\/~gacs\/papers\/ait-notes.pdf"},{"key":"9527_CR5","first-page":"254","volume-title":"Essays in Memory of Shimon Even","author":"O. Goldreich","year":"2006","unstructured":"Goldreich, O.: On promise problems: a survey. In: Essays in Memory of Shimon Even, pp. 254\u2013290 (2006). ECCC TR05-018"},{"key":"9527_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"2008","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"9527_CR7","first-page":"1","volume-title":"Proc. ACM STOC","author":"A. Rao","year":"2008","unstructured":"Rao, A.: Parallel repetition in projection games and a concentration bound. In:\u00a0Proc. ACM STOC, pp.\u00a01\u201310 (2008). ECCC TR08-013"},{"issue":"5","key":"9527_CR8","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997). Earlier version in IEEE FOCS 1994. quant-ph\/9508027","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9527_CR9","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9527-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9527-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9527-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:26Z","timestamp":1558698866000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9527-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,15]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["9527"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9527-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12,15]]}}}