{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:58:59Z","timestamp":1725469139189},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_31","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"362-373","source":"Crossref","is-referenced-by-count":0,"title":["Testing Permanent Oracles \u2013 Revisited"],"prefix":"10.1007","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnab","family":"Bhattacharyya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajsekar","family":"Manokaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Arkhipov, A.: The computational complexity of linear optics. In: Fortnow, L., Vadhan, S.P. (eds.) Proc. 43rd Annual ACM Symposium on the Theory of Computing, pp. 333\u2013342. ACM (2011)","DOI":"10.1145\/1993636.1993682"},{"issue":"2","key":"31_CR2","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comp. Sci.\u00a08(2), 189\u2013201 (1979)","journal-title":"Theor. Comp. Sci."},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, pp. 124\u2013134. IEEE Computer Society (1994)","DOI":"10.1109\/SFCS.1994.365700"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Broder, A.Z.: How hard is to marry at random (on the approximation of the permanent). In: Hartmanis, J. (ed.) Proc. 18th Annual ACM Symposium on the Theory of Computing, pp. 50\u201358. ACM (1986)","DOI":"10.1145\/12130.12136"},{"issue":"6","key":"31_CR5","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M. Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM J. on Comput.\u00a018(6), 1149\u20131178 (1989)","journal-title":"SIAM J. on Comput."},{"issue":"4","key":"31_CR6","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1145\/1008731.1008738","volume":"51","author":"M. Jerrum","year":"2004","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM\u00a051(4), 671\u2013697 (2004)","journal-title":"J. ACM"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Gemmell, P., Lipton, R.J., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing\/correcting for polynomials and for approximate functions. In: Koutsougeras, C., Vitter, J.S. (eds.) Proc. 23rd Annual ACM Symposium on the Theory of Computing, pp. 32\u201342. ACM (1991)","DOI":"10.1145\/103418.103429"},{"issue":"4","key":"31_CR8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(92)90195-2","volume":"43","author":"P. Gemmell","year":"1992","unstructured":"Gemmell, P., Sudan, M.: Highly resilient correctors for polynomials. Inform. Process. Lett.\u00a043(4), 169\u2013174 (1992)","journal-title":"Inform. Process. Lett."},{"key":"31_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/3-540-49116-3_8","volume-title":"STACS 99","author":"J.-Y. Cai","year":"1999","unstructured":"Cai, J.-Y., Pavan, A., Sivakumar, D.: On the Hardness of Permanent. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 90\u201399. Springer, Heidelberg (1999)"},{"issue":"4","key":"31_CR10","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"issue":"2","key":"31_CR11","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0022-0000(03)00012-6","volume":"67","author":"S. Arora","year":"2003","unstructured":"Arora, S., Khot, S.: Fitting algebraic curves to noisy data. J. Comp. Sys. Sci.\u00a067(2), 325\u2013340 (2003)","journal-title":"J. Comp. Sys. Sci."}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:05:30Z","timestamp":1620129930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}