{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T21:55:21Z","timestamp":1693000521094},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1990,3,1]],"date-time":"1990-03-01T00:00:00Z","timestamp":636249600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1990,3]]},"DOI":"10.1007\/bf02122692","type":"journal-article","created":{"date-parts":[[2005,9,14]],"date-time":"2005-09-14T15:44:43Z","timestamp":1126712683000},"page":"3-25","source":"Crossref","is-referenced-by-count":16,"title":["On the power of interaction"],"prefix":"10.1007","volume":"10","author":[{"given":"W.","family":"Aiello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Goldwasser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Hastad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02122692_CR1","doi-asserted-by":"crossref","unstructured":"W.Aiello, S.Goldwasser and J.Hastad, On the Power of Interaction,Proc. of the 27th IEEE Symposium on Foundations of Computer Science, 368\u2013379, Toronto,1986.","DOI":"10.1109\/SFCS.1986.36"},{"key":"BF02122692_CR2","doi-asserted-by":"crossref","unstructured":"L.Babai, Trading Group Theory for Randomness,Proc. of the 17th ACM Symposium on Theory of Computing, 421\u2013429, Providence,1985.","DOI":"10.1145\/22145.22192"},{"issue":"No. 2","key":"BF02122692_CR3","first-page":"254","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai andS. Moran, Arthur-Merlin Games: a Randomized Proof System, and a Hierarchy of Complexity Classes,JCSS,36 (1988), No. 2, 254\u2013276.","journal-title":"JCSS"},{"issue":"No. 2","key":"BF02122692_CR4","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"R. Boppana, J. Hastad andS. Zachos, Doesco-NP have Short Interactive Proofs?,Information Processing Letters,25 (1987), No. 2, 127\u2013132.","journal-title":"Information Processing Letters"},{"key":"BF02122692_CR5","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","volume":"28","author":"L. Fortnow","year":"1988","unstructured":"L. Fortnow andM. Sipser, Are There Interactive Protocols forco-NP?,Information Processing Letters,28 (1988), 249\u2013251.","journal-title":"Information Processing Letters"},{"key":"BF02122692_CR6","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe andM. Sipser, Parity, Circuits, and the Polynomial Time Hierarchy,Math. System Theory,17 (1984), 13\u201327.","journal-title":"Math. System Theory"},{"key":"BF02122692_CR7","doi-asserted-by":"crossref","unstructured":"O.Goldreich, Y.Mansour and M.Sipser, Interactive Proof Systems: Provers that Never Fail and Random Selection,Proc. of the 28th IEEE Symposium on Foundations of Computer Science, 449\u2013461, Los Angeles,1987.","DOI":"10.1109\/SFCS.1987.35"},{"key":"BF02122692_CR8","unstructured":"S.Goldwasser, S.Micali and C.Rackoff, The Knowledge Complexity of Interactive Proofs,Proc. of the 17th ACM Symposium on Theory of Computing, 291\u2013305, Providence,1985, also inSIAM J. on Computing.18 (1989), No. 1, 186\u2013208."},{"key":"BF02122692_CR9","doi-asserted-by":"crossref","unstructured":"S.Goldwasser and M.Sipser, Private Coins vs. Public Coins in Interactive Proof Systems,Proc. of the 18th ACM Symposium on Theory of Computing, 59\u201368, Berkeley,1986.","DOI":"10.1145\/12130.12137"},{"key":"BF02122692_CR10","doi-asserted-by":"crossref","unstructured":"J.Hastad, Almost Optimal Lower Bounds for Small Depth Circuits,Proc. of the 18th ACM Symposium on Theory of Computing, 6\u201320, Berkeley,1986.","DOI":"10.1145\/12130.12132"},{"key":"BF02122692_CR11","unstructured":"J.Hastad,Computational Limitations of Small Depth Circuits, Ph. D. thesis, MIT,1986."},{"key":"BF02122692_CR12","doi-asserted-by":"crossref","unstructured":"N.Nisan and A.Wigderson, Hardness vs. Randomness,Proc. of the 29th IEEE Symposium on Foundations of Computer Science, 2\u201311, White Plains,1988.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"BF02122692_CR13","doi-asserted-by":"crossref","unstructured":"M.Sipser, Borel Sets and Circuit Complexity,Proc. of the 15th ACM Symposium on Theory of Computing, 61\u201369, Boston,1983.","DOI":"10.1145\/800061.808733"},{"key":"BF02122692_CR14","doi-asserted-by":"crossref","unstructured":"A.Yao, Separating the Polynomial-Time Hierarchy by Oracles,Proc. of the 26th IEEE Symposium on Foundations of Computer Science, 1\u201310, Portland,1985.","DOI":"10.1109\/SFCS.1985.49"},{"key":"BF02122692_CR15","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/3-540-16486-3_112","volume":"233","author":"S. Zachos","year":"1986","unstructured":"S. Zachos, Probabilistic Quantifiers, Adversaries and Complexity Classes; An Overview,Structures in Complexity Theory, Lecture Notes in Computer Science,233 (1986), 383\u2013398.","journal-title":"Lecture Notes in Computer Science"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02122692.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02122692\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02122692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T12:58:06Z","timestamp":1586437086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02122692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,3]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,3]]}},"alternative-id":["BF02122692"],"URL":"https:\/\/doi.org\/10.1007\/bf02122692","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,3]]}}}