{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T06:45:49Z","timestamp":1725432349982},"reference-count":26,"publisher":"IEEE Comput. Soc. Press","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sct.1994.315796","type":"proceedings-article","created":{"date-parts":[[2002,12,17]],"date-time":"2002-12-17T14:32:51Z","timestamp":1040135571000},"page":"280-293","source":"Crossref","is-referenced-by-count":4,"title":["Random debaters and the hardness of approximating stochastic functions"],"prefix":"10.1109","author":[{"given":"A.","family":"Condon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Feigenbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Lund","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Shor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167190"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167190"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/321978.321989"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185341"},{"journal-title":"Computers and Intractability A Guide to the Theory of NP-Completeness","year":"1979","author":"garey","key":"ref14"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1994.315789"},{"key":"ref16","first-page":"67","author":"johnson","year":"1990","journal-title":"Handbook of Theoretical Computer Science Volume A Algorithms and Complexity"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167172"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56939-1_63"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267824"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195129"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"ref8","first-page":"757","author":"boppana","year":"1990","journal-title":"Handbook of Theoretical Computer Science Volume A Algorithms and Complexity"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054191000091"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267823"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"ref1","first-page":"471","article-title":"A theorem on probabilistic constant depth circuits","author":"ajtai","year":"1984","journal-title":"Proc 16th Annual ACM Symposium on Theory of Computing"},{"key":"ref20","article-title":"Approximation Schemes for PSPACE-Complete Problems for Succinct Representation","author":"marathe","year":"1994","journal-title":"Proc 26th Symposium on Theory of Computing"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90045-5"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802475"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90045-4"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"journal-title":"Efficient checking of polynomials and proofs and the hardness of approximation problems","year":"1992","author":"sudan","key":"ref25"}],"event":{"name":"IEEE 9th Annual Conference on Structure in Complexity Theory","acronym":"SCT-94","location":"Amsterdam, Netherlands"},"container-title":["Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx2\/967\/7616\/00315796.pdf?arnumber=315796","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,3,9]],"date-time":"2017-03-09T10:16:38Z","timestamp":1489054598000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/315796\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":26,"URL":"https:\/\/doi.org\/10.1109\/sct.1994.315796","relation":{},"subject":[]}}