{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:20Z","timestamp":1725488540132},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540401766"},{"type":"electronic","value":"9783540448495"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44849-7_26","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:26:17Z","timestamp":1186727177000},"page":"213-226","source":"Crossref","is-referenced-by-count":0,"title":["Nearly Bounded Error Probabilistic Sets"],"prefix":"10.1007","author":[{"given":"Tomoyuki","family":"Yamakami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"26_CR1","first-page":"1402","volume":"E84-D","author":"S. Aida","year":"2001","unstructured":"S. Aida and T. Tsukiji, P-comp versus P-samp questions on average polynomial domination. IEICE Trans. Inf. & Syst., E84-D (2001), 1402\u20131410.","journal-title":"IEICE Trans. Inf. & Syst."},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"L. Babai, L. Fortnow, N. Nisan, and A. Wigderson, BPP has subexponential time simulation unless EXPTIME has publishable proofs, Comput. Complexity, 3 (1993), 307\u2013318.","journal-title":"Comput. Complexity"},{"key":"26_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/3-540-49116-3_9","volume-title":"Proc. 16th Symposium on Theoretical Aspects of Computer Science","author":"H. Buhrman","year":"1999","unstructured":"H. Buhrman and L. Fortnow, One-sided versus two-sided error in probabilistic computation, Proc. 16th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 1563, pp. 100\u2013109, 1999."},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"887","DOI":"10.1137\/S009753979834388X","volume":"31","author":"H. Buhrman","year":"2002","unstructured":"H. Buhrman, L. Fortnow, and S. Laplante, Resource-bounded Kolmogorov complexity revisited, SIAM J. Comput., 31 (2002), 887\u2013905.","journal-title":"SIAM J. Comput."},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1137\/S0097539799360148","volume":"30","author":"H. Buhrman","year":"2000","unstructured":"H. Buhrman and L. Torenvliet, Randomness is hard, SIAM J. Comput., 30 (2000), 1485\u20131501.","journal-title":"SIAM J. Comput."},{"key":"26_CR6","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S. Even","year":"1984","unstructured":"S. Even, A. Selman, and Y. Yacobi, The complexity of promise problems with applications to public-key cryptography, Inform. and Control, 61 (1984), 159\u2013173.","journal-title":"Inform. and Control"},{"key":"26_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/3-540-10003-2_71","volume-title":"Proc. 7th Colloquium on Automata, Languages and Programming","author":"S. Even","year":"1980","unstructured":"S. Even and Y. Yacobi, Cryptocomplexity and NP-completeness, in Proc. 7th Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 85, pp. 195\u2013207, 1980."},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J. Feigenbaum","year":"1993","unstructured":"J. Feigenbaum and L. Fortnow, Random-self-reducibility of complete sets, SIAM J. Comput., 22 (1993), 994\u20131005.","journal-title":"SIAM J. Comput."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum, S. Kannan, and N. Nisan, Lower bounds on random-self-reducibility, in Proc. 5th Structure in Complexity Theory Conference, pp. 100\u2013109, 1990.","DOI":"10.1109\/SCT.1990.113959"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Y. Gurevich, Average case complexity, J. Comput. System Sci., 42 (1991), 346\u2013398.","journal-title":"J. Comput. System Sci."},{"key":"26_CR11","first-page":"191","volume":"28","author":"R. M. Karp","year":"1982","unstructured":"R. M. Karp and R. Lipton, Turing machines that take advice, L\u2019enseigment Mathematique, 28 (1982), 191\u2013209.","journal-title":"L\u2019enseigment Mathematique"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C. Lautemann","year":"1983","unstructured":"C. Lautemann, BPP and the polynomial hierarchy, Inform. Process. Lett., 17 (1983), 215\u2013217.","journal-title":"Inform. Process. Lett."},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. A. Levin","year":"1986","unstructured":"L. A. Levin, Average case complete problems, SIAM J. Comput., 15 (1986), 285\u2013286.","journal-title":"SIAM J. Comput."},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"M. Li and P. Vit\u00e1nyi, An Introduction to Kolmogorov Complexity and Its Applications (second edition), Springer, 1997.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"A. Meyer and L. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, in Proc. 13th Symposium on Switching and Automata, pp. 125\u2013129, 1972.","DOI":"10.1109\/SWAT.1972.29"},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and A. Wigderson, Hardness vs. randomness, J. Comput. System Sci., 49 (1994), 149\u2013167.","journal-title":"J. Comput. System Sci."},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"C. Schindelhauer and A. Jakoby, The non-recursive power of erroneous computation, in Proc. 19th Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 394\u2013406, 1999.","DOI":"10.1007\/3-540-46691-6_32"},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/0022-0000(89)90020-2","volume":"39","author":"U. Sch\u00f6ning","year":"1989","unstructured":"U. Sch\u00f6ning, Probabilistic complexity classes and lowness, J. Comput. System Sci., 39 (1989), 84\u2013100.","journal-title":"J. Comput. System Sci."},{"key":"26_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1007\/BFb0030859","volume-title":"Proc. 1st International Computing and Combinatorics Conference","author":"R. Schuler","year":"1995","unstructured":"R. Schuler and T. Yamakami, Sets computable in polynomial time on average, in Proc. 1st International Computing and Combinatorics Conference, Lecture Notes in Computer Science, Vol. 959, pp. 400\u2013409, 1995."},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"M. Sipser, A complexity theoretic approach to randomness, in Proc. 15th ACM Symposium on Theory of Computing, pp. 330\u2013335, 1983.","DOI":"10.1145\/800061.808762"},{"key":"26_CR21","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1006\/jcom.1999.0523","volume":"15","author":"T. Yamakami","year":"1999","unstructured":"T. Yamakami, Polynomial time samplable distributions, J. Complexity, 15 (1999), 557\u2013574. A preliminary version appeared in Proc. 21th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 1113, pp. 566\u2013578, 1996.","journal-title":"J. Complexity"},{"key":"26_CR22","unstructured":"T. Yamakami, Average Case Complexity Theory, Ph.D. dissertation, Department of Computer Science, University of Toronto, 1997. Available as Technical Report 307\/97, University of Toronto. Also available at ECCC Thesis Listings."},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"D. Zuckerman, Randomness-optimal sampling, extractors, and constructive leader election, in Proc. 28th ACM Symposium on Theory of Computing, pp. 286\u2013295, 1996.","DOI":"10.1145\/237814.237878"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44849-7_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T02:21:07Z","timestamp":1550715667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44849-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540401766","9783540448495"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-44849-7_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}