{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:23Z","timestamp":1763468003973,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_13","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"140-151","source":"Crossref","is-referenced-by-count":12,"title":["Polynomial-Space Approximation of No-Signaling Provers"],"prefix":"10.1007","author":[{"given":"Tsuyoshi","family":"Ito","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"13_CR1","doi-asserted-by":"publisher","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. Computational Complexity\u00a01(1), 3\u201340 (1991)","journal-title":"Computational Complexity"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Beckman, D., Gottesman, D., Nielsen, M.A., Preskill, J.: Causal and localizable quantum operations. Physical Review A 64(052309) (2001)","DOI":"10.1103\/PhysRevA.64.052309"},{"key":"13_CR3","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195","volume":"1","author":"J.S. Bell","year":"1964","unstructured":"Bell, J.S.: On the Einstein-Podolsky-Rosen paradox. Physics\u00a01, 195\u2013200 (1964)","journal-title":"Physics"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: How to remove intractability assumptions. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC), pp. 113\u2013131 (1988)","DOI":"10.1145\/62212.62223"},{"issue":"4","key":"13_CR5","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"Borodin, A.: On relating time and space to size and depth. SIAM Journal on Computing\u00a06(4), 733\u2013744 (1977)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"13_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0022-0000(05)80026-1","volume":"48","author":"J.Y. Cai","year":"1994","unstructured":"Cai, J.Y., Condon, A., Lipton, R.J.: PSPACE is provable by two provers in one round. Journal of Computer and System Sciences\u00a048(1), 183\u2013193 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Cleve, R., H\u00f8yer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: Proceedings: Nineteenth Annual IEEE Conference on Computational Complexity (CCC), pp. 236\u2013249 (2004)","DOI":"10.1109\/CCC.2004.1313847"},{"issue":"2","key":"13_CR8","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S. Even","year":"1984","unstructured":"Even, S., Selman, A.L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Information and Control\u00a061(2), 159\u2013173 (1984)","journal-title":"Information and Control"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Feige, U.: On the success probability of the two provers in one-round proof systems. In: Proceedings of the Sixth Annual Structure in Complexity Theory Conference (SCT), pp. 116\u2013123 (1991)","DOI":"10.1109\/SCT.1991.160251"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U., Lov\u00e1sz, L.: Two-prover one-round proof systems: Their power and their problems. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (STOC), pp. 733\u2013744 (1992)","DOI":"10.1145\/129712.129783"},{"issue":"2","key":"13_CR11","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/0304-3975(94)90251-8","volume":"134","author":"L. Fortnow","year":"1994","unstructured":"Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols. Theoretical Computer Science\u00a0134(2), 545\u2013557 (1994)","journal-title":"Theoretical Computer Science"},{"key":"13_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"O. Goldreich","year":"2008","unstructured":"Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008)"},{"issue":"9\u201310","key":"13_CR13","doi-asserted-by":"crossref","first-page":"739","DOI":"10.26421\/QIC9.9-10-2","volume":"9","author":"G. Gutoski","year":"2009","unstructured":"Gutoski, G.: Properties of local quantum operations with shared entanglement. Quantum Information and Computation\u00a09(9\u201310), 739\u2013764 (2009)","journal-title":"Quantum Information and Computation"},{"key":"13_CR14","unstructured":"Holenstein, T.: Parallel repetition: Simplifications and the no-signaling case. Theory of Computing 5(Article\u00a08), 141\u2013172 (2009)"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Ito, T., Kobayashi, H., Matsumoto, K.: Oracularization and two-prover one-round interactive proofs against nonlocal strategies. In: Proceedings: Twenty-Fourth Annual IEEE Conference on Compuational Complexity (CCC), pp. 217\u2013228 (2009)","DOI":"10.1109\/CCC.2009.22"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Ito, T., Kobayashi, H., Preda, D., Sun, X., Yao, A.C.C.: Generalized Tsirelson inequalities, commuting-operator provers, and multi-prover interactive proof systems. In: Proceedings: Twenty-Third Annual IEEE Conference on Compuational Complexity (CCC), pp. 187\u2013198 (2008)","DOI":"10.1109\/CCC.2008.12"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Jain, R., Ji, Z., Upadhyay, S., Watrous, J.: QIP=PSPACE. In: Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing STOC (2010) (to appear) arXiv:0907.4737v2 [quant-ph]","DOI":"10.1145\/1806689.1806768"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Jain, R., Upadhyay, S., Watrous, J.: Two-message quantum interactive proofs are in PSPACE. In: Proceedings: Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 534\u2013543 (2009)","DOI":"10.1109\/FOCS.2009.30"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Jain, R., Watrous, J.: Parallel approximation of non-interactive zero-sum quantum games. In: Proceedings: Twenty-Fourth Annual IEEE Conference on Compuational Complexity (CCC), pp. 243\u2013253 (2009)","DOI":"10.1109\/CCC.2009.26"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Kempe, J., Kobayashi, H., Matsumoto, K., Toner, B., Vidick, T.: Entangled games are hard to approximate. arXiv:0704.2903v2 [quant-ph] (2007)","DOI":"10.1109\/FOCS.2008.8"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Kempe, J., Kobayashi, H., Matsumoto, K., Toner, B., Vidick, T.: Entangled games are hard to approximate. In: Proceedings: Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 447\u2013456 (2008)","DOI":"10.1109\/FOCS.2008.8"},{"key":"13_CR22","unstructured":"Khalfin, L.A., Tsirelson, B.S.: Quantum and quasi-classical analogs of Bell inequalities. In: Symposium on the Foundations of Modern Physics, pp. 441\u2013460 (1985)"},{"issue":"3","key":"13_CR23","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/S0022-0000(03)00035-7","volume":"66","author":"H. Kobayashi","year":"2003","unstructured":"Kobayashi, H., Matsumoto, K.: Quantum multi-prover interactive proof systems with limited prior entanglement. Journal of Computer and System Sciences\u00a066(3), 429\u2013450 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"13_CR24","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S.A. Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research\u00a020(2), 257\u2013301 (1995)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"13_CR25","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF02058098","volume":"24","author":"S. Popescu","year":"1994","unstructured":"Popescu, S., Rohrlich, D.: Quantum nonlocality as an axiom. Foundations of Physics\u00a024(3), 379\u2013385 (1994)","journal-title":"Foundations of Physics"},{"key":"13_CR26","unstructured":"Preda, D.: Private communication"},{"issue":"9","key":"13_CR27","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1007\/BF00739036","volume":"15","author":"P. Rastall","year":"1985","unstructured":"Rastall, P.: Locality, Bell\u2019s theorem, and quantum mechanics. Foundations of Physics\u00a015(9), 963\u2013972 (1985)","journal-title":"Foundations of Physics"},{"key":"13_CR28","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Chichester (1986)"},{"issue":"3","key":"13_CR29","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0292(3), 575\u2013588 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"13_CR30","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF00399761","volume":"14","author":"R.F. Werner","year":"1989","unstructured":"Werner, R.F.: An application of Bell\u2019s inequatilies to a quantum state extension problem. Letters in Mathematical Physics\u00a014(4), 359\u2013363 (1989)","journal-title":"Letters in Mathematical Physics"},{"issue":"4","key":"13_CR31","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF00429951","volume":"19","author":"R.F. Werner","year":"1990","unstructured":"Werner, R.F.: Remarks on a quantum state extension problem. Letters in Mathematical Physics\u00a019(4), 319\u2013326 (1990)","journal-title":"Letters in Mathematical Physics"},{"key":"13_CR32","doi-asserted-by":"crossref","unstructured":"Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: Proceedings: Forty-Second IEEE Symposium on Foundations of Computer Science (FOCS), pp. 538\u2013546 (2001)","DOI":"10.1109\/SFCS.2001.959930"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:31:28Z","timestamp":1740241888000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}