{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:56Z","timestamp":1760202536160,"version":"3.33.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T00:00:00Z","timestamp":1190073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s00453-007-9033-6","type":"journal-article","created":{"date-parts":[[2007,9,17]],"date-time":"2007-09-17T18:41:42Z","timestamp":1190054502000},"page":"462-489","source":"Crossref","is-referenced-by-count":3,"title":["Quantum Information and the PCP Theorem"],"prefix":"10.1007","volume":"55","author":[{"given":"Ran","family":"Raz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,18]]},"reference":[{"issue":"1","key":"9033_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2005.v001a001","volume":"1","author":"S. Aaronson","year":"2005","unstructured":"Aaronson, S.: Limitations of quantum advice and one-way communication. Theory Comput. 1(1), 1\u201328 (2005)","journal-title":"Theory Comput."},{"key":"9033_CR2","volume-title":"Annual Review of Computational Physics","author":"D. Aharonov","year":"1998","unstructured":"Aharonov, D.: Quantum Computation\u2014A Review. In: Stauffer, D. (ed.) Annual Review of Computational Physics, vol.\u00a0VI. World Scientific, Singapore (1998)"},{"issue":"3","key":"9033_CR3","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"9033_CR4","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1145\/581771.581773","volume":"49","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A., Nayak, A., Ta-Shma, A., Vazirani, U.V.: Dense quantum coding and quantum finite automata. J. ACM 49(4), 496\u2013511 (2002)","journal-title":"J. ACM"},{"issue":"1","key":"9033_CR5","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"9033_CR6","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. Combinatorica 23(3), 365\u2013426 (2003)","journal-title":"Combinatorica"},{"key":"9033_CR7","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. STOC 421\u2013429 (1985)","DOI":"10.1145\/22145.22192"},{"issue":"2","key":"9033_CR8","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254\u2013276 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9033_CR9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3\u201340 (1991)","journal-title":"Comput. Complex."},{"key":"9033_CR10","unstructured":"Cleve, R., Hoyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. IEEE Conf. Comput. Complex. (2004) 236\u2013249"},{"key":"9033_CR11","unstructured":"Dinur, I., Fischer, E., Kindler, G., Raz, R., Safra, S.: PCP characterizations of NP: towards a polynomially-small error-probability. STOC 29-40 (1999). Full version in http:\/\/www.wisdom.weizmann.ac.il\/~ranraz\/publications"},{"issue":"2","key":"9033_CR12","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"issue":"1","key":"9033_CR13","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9033_CR14","first-page":"3","volume":"9","author":"A.S. Holevo","year":"1973","unstructured":"Holevo, A.S.: Some estimates for the amount of information transmittable by a quantum communications channel. Probl. Peredaci Inf. 9(3), 3\u201311 (1973). English translation: Probl. Inf. Trans. 9(3), 177\u2013183 (1973)","journal-title":"Probl. Peredaci Inf."},{"key":"9033_CR15","doi-asserted-by":"crossref","unstructured":"Kitaev, A., Watrous, J.: Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. STOC 608\u2013617 (2000)","DOI":"10.1145\/335305.335387"},{"issue":"4","key":"9033_CR16","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"key":"9033_CR17","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Sub-constant error low degree test of almost-linear size. STOC 21\u201330 (2006)","DOI":"10.1145\/1132516.1132520"},{"key":"9033_CR18","doi-asserted-by":"crossref","unstructured":"Nayak, A.: Optimal lower bounds for quantum automata and random access codes. FOCS 369\u2013377 (1999)","DOI":"10.1109\/SFFCS.1999.814608"},{"key":"9033_CR19","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"9033_CR20","unstructured":"Nishimura, H., Yamakami, T.: Polynomial time quantum computation with advice. Electronic Colloquium on Computational Complexity (ECCC)(059) (2003)"},{"issue":"3","key":"9033_CR21","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"9033_CR22","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test and a sub-constant error-probability PCP characterization of NP. STOC 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"issue":"2","key":"9033_CR23","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9033_CR24","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP\u2009=\u2009PSPACE. J. ACM 39(4), 869\u2013877 (1992)","journal-title":"J. ACM"},{"issue":"3","key":"9033_CR25","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1016\/S0304-3975(01)00375-9","volume":"292","author":"J. Watrous","year":"2003","unstructured":"Watrous, J.: PSPACE has constant-round quantum interactive proof systems. Theor. Comput. Sci. 292(3), 575\u2013588 (2003)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9033-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9033-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9033-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T01:12:09Z","timestamp":1737421929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9033-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,18]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["9033"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9033-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2007,9,18]]}}}