{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T20:40:02Z","timestamp":1736109602314,"version":"3.32.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":19,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354019021X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0026095","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:47:21Z","timestamp":1132645641000},"page":"40-51","source":"Crossref","is-referenced-by-count":14,"title":["On counting and approximation"],"prefix":"10.1007","author":[{"given":"Johannes","family":"K\u00f6bler","sequence":"first","affiliation":[]},{"given":"Uwe","family":"Sch\u00f6ning","sequence":"additional","affiliation":[]},{"given":"Jacobo","family":"Toran","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"E.W.Allender, Invertible functions, Ph.D. Thesis, Georgia Institute of Technology, 1985."},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"L. Babai, Trading group theory for randomness, Proc. 17th STOC, 1985, 421\u2013429.","DOI":"10.1145\/22145.22192"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"R.B. Boppana, J. Hastad and S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters 25, 1987, 127\u2013132.","journal-title":"Information Processing Letters"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"A.V. Goldberg and M.Sipser, Compresion and ranking, Proc. 17th STOC, 1985, 440\u2013448.","DOI":"10.1145\/22145.22194"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"S. Goldwasser and M. Sipser, Private coins versus public coins in interactive proof systems, Proc. 18th STOC, 1986, 59\u201368.","DOI":"10.1145\/12130.12137"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"S. Grollmann and A.L. Selman, Complexity measures for publik-key crypto-systems, Proc. 25th FOCS 1984, 495\u2013503.","DOI":"10.1109\/SFCS.1984.715952"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"L. Hemachandra, On ranking, Proc. 2nd Structure in Complexity Theory Conf., 1987, 103\u2013117.","DOI":"10.1109\/PSCT.1987.10319259"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"M.W. Krentel, The complexity of optimization problems, Proc. 18th STOC 1986, 69\u201376.","DOI":"10.1145\/12130.12138"},{"key":"4_CR9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"M.R. Jerrum, L.G. Valiant and V.V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theor. Comput. Sci. 43 (1986), 169\u2013188","journal-title":"Theor. Comput. Sci."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning, Graph isomorphism is in the low hierarchy, Proc. 4th STACS 1987, Lecture Notes in Comput. Science, 114\u2013124.","DOI":"10.1007\/BFb0039599"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"M. Sipser, A complexity theoretic approach to randomness, Proc. 15th STOC, 1983, 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"4_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer, The polynomial time hierarchy, Theoret. Comput. Science 3 (1977), 1\u201322.","journal-title":"Theoret. Comput. Science"},{"key":"4_CR13","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1137\/0214060","volume":"14","author":"L. Stockmeyer","year":"1985","unstructured":"L. Stockmeyer, On approximation algorithms for #P, SIAM Journ. on Comput. 14 (1985), 849\u2013861.","journal-title":"SIAM Journ. on Comput."},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L.G. Valiant","year":"1976","unstructured":"L.G. Valiant, Relative complexity of checking and evaluating, Inform. Proc. Letters 5 (1976), 20\u201323.","journal-title":"Inform. Proc. Letters"},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"L.G. Valiant, The complexity of computing the permanent, Theor. Comput. Sci. 8 (1979), 189\u2013201.","journal-title":"Theor. Comput. Sci."},{"key":"4_CR16","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"L.G. Valiant, The complexity of enumeration and reliability problems, SIAM Journ. Comput. 8 (1979), 410\u2013421.","journal-title":"SIAM Journ. Comput."},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(86)90141-6","volume":"47","author":"K.W. Wagner","year":"1986","unstructured":"K.W. Wagner, Some observations on the connection between counting and recursion, Theor. Comput. Sci. 47 (1986), 131\u2013147.","journal-title":"Theor. Comput. Sci."},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"S. Zachos, Probabilistic quantifiers, adversaries, and complexity classes: an overview, Proc. Structure in Complexity Theory Conf. 1986, Lecture Notes in Comput Science, Springer, 383\u2013400.","DOI":"10.1007\/3-540-16486-3_112"},{"key":"4_CR19","unstructured":"S. Zachos and M. F\u00fcrer, Probabilistic quantifiers vs. distrustful adversaries, manuscript, 1985."}],"container-title":["Lecture Notes in Computer Science","CAAP '88"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0026095.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T20:08:00Z","timestamp":1736107680000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0026095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354019021X"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0026095","relation":{},"subject":[]}}