{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:47:38Z","timestamp":1725587258970},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_6","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"61-72","source":"Crossref","is-referenced-by-count":1,"title":["Advice Coins for Classical and Quantum Computation"],"prefix":"10.1007","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Drucker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: BQP and the polynomial hierarchy. In: Proc. 42nd ACM STOC (2010)","DOI":"10.1145\/1806689.1806711"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1098\/rspa.2008.0350","volume":"465","author":"S. Aaronson","year":"2009","unstructured":"Aaronson, S., Watrous, J.: Closed timelike curves make quantum and classical computing equivalent. Proc. Roy. Soc. London A\u00a0465, 631\u2013647 (2009)","journal-title":"Proc. Roy. Soc. London A"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: \u03a31 1-formulae on finite structures. Ann. Pure Appl. Logic\u00a024, 1\u201348 (1983)","journal-title":"Ann. Pure Appl. Logic"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-02927-1_7","volume-title":"Automata, Languages and Programming","author":"K. Amano","year":"2009","unstructured":"Amano, K.: Bounds on the size of small depth circuits for approximating majority. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 59\u201370. Springer, Heidelberg (2009)"},{"key":"6_CR5","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S. Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer-Verlag New York, Inc., Secaucus (2006)"},{"issue":"4","key":"6_CR6","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"Borodin, A.: On relating time and space to size and depth. SIAM J. Comput.\u00a06(4), 733\u2013744 (1977)","journal-title":"SIAM J. Comput."},{"issue":"1-3","key":"6_CR7","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0019-9958(83)80060-6","volume":"58","author":"A. Borodin","year":"1983","unstructured":"Borodin, A., Cook, S., Pippenger, N.: Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control\u00a058(1-3), 113\u2013136 (1983)","journal-title":"Information and Control"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A., Raz, R., Yehudayoff, A.: Pseudorandom generators for regular branching programs. In: Proc. 51st IEEE FOCS (2010)","DOI":"10.1109\/FOCS.2010.11"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Brody, J., Verbin, E.: The coin problem, and pseudorandomness for branching programs. In: Proc. 51st IEEE FOCS (2010)","DOI":"10.1109\/FOCS.2010.10"},{"issue":"3","key":"6_CR10","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1214\/aoms\/1177697590","volume":"40","author":"T.M. Cover","year":"1969","unstructured":"Cover, T.M.: Hypothesis testing with finite statistics. Ann. Math. Stat.\u00a040(3), 828\u2013835 (1969)","journal-title":"Ann. Math. Stat."},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Galvao, E.F., Hardy, L.: Substituting a qubit for an arbitrarily large number of classical bits. Phys. Rev. Lett. 90(087902) (2003)","DOI":"10.1103\/PhysRevLett.90.087902"},{"key":"6_CR12","unstructured":"Hellman, E.M.: Learning with finite memory. PhD thesis, Stanford University, Department of Electrical Engineering (1969)"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1214\/aoms\/1177696958","volume":"41","author":"E.M. Hellman","year":"1970","unstructured":"Hellman, E.M., Cover, T.M.: Learning with finite memory. Ann. of Math. Stat.\u00a041, 765\u2013782 (1970)","journal-title":"Ann. of Math. Stat."},{"issue":"3","key":"6_CR14","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/S0022-0000(05)80061-3","volume":"48","author":"C.A. Neff","year":"1994","unstructured":"Neff, C.A.: Specified precision polynomial root isolation is in NC. J. Comput. Sys. Sci.\u00a048(3), 429\u2013463 (1994)","journal-title":"J. Comput. Sys. Sci."},{"issue":"2","key":"6_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1006\/jcom.1996.0008","volume":"12","author":"C.A. Neff","year":"1996","unstructured":"Neff, C.A., Reif, J.H.: An efficient algorithm for the complex roots problem. J. Complexity\u00a012(2), 81\u2013115 (1996)","journal-title":"J. Complexity"},{"key":"6_CR16","volume-title":"Quantum Computation and Quantum Information","author":"M. Nielsen","year":"2000","unstructured":"Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-540-73420-8_19","volume-title":"Automata, Languages and Programming","author":"R. O\u2019Donnell","year":"2007","unstructured":"O\u2019Donnell, R., Wimmer, K.: Approximation by DNF: examples and counterexamples. In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 195\u2013206. Springer, Heidelberg (2007)"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Pan, V.Y.: Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros. In: Proc. 27th ACM STOC, pp. 741\u2013750 (1995)","DOI":"10.1145\/225058.225292"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Terhal, B., DiVincenzo, D.: On the problem of equilibration and the computation of correlation functions on a quantum computer. Phys. Rev. A 61(022301) (2000)","DOI":"10.1103\/PhysRevA.61.022301"},{"issue":"3","key":"6_CR20","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s00037-009-0267-3","volume":"18","author":"E. Viola","year":"2009","unstructured":"Viola, E.: On approximate majority and probabilistic time. Computational Complexity\u00a018(3), 155\u2013168 (2009)","journal-title":"Computational Complexity"},{"key":"6_CR21","unstructured":"Viola., E.: Randomness buys depth for approximate counting. Electronic Colloquium on Computational Complexity (ECCC), TR10-175 (2010)"},{"issue":"2","key":"6_CR22","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1006\/jcss.1999.1655","volume":"59","author":"J. Watrous","year":"1999","unstructured":"Watrous., J.: Space-bounded quantum complexity. J. Comput. Sys. Sci.\u00a059(2), 281\u2013326 (1999)","journal-title":"J. Comput. Sys. Sci."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T01:47:47Z","timestamp":1560304067000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}