Alex Wright
Skip Abstract Section
Abstract
Researchers are making headway with one of quantum computing's major theoretical problems: multi-prover interactive proofs.
- László Babai, Lance Fortnow, Carsten Lund. Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. Computational Complexity, 1, 1 (1991), 3-40.Google Scholar
- A.K. Ekert, Quantum Cryptography Based on Bell's Theorem, Physical Review Letters, vol. 67, no. 6, 5 August 1991, pp. 661-663.Google ScholarCross Ref
- Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for NEXP sound against entangled provers, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, September 2012. arXiv:1207.0550v2. Google ScholarDigital Library
- Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. 2010. QIP = PSPACE. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC '10). ACM, New York, NY, USA, 573-582. DOI=10.1145/1806689.1806768 http://doi.acm.org/10.1145/1806689.1806768 Google ScholarDigital Library
- Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick 2011. Entangled Games Are Hard to Approximate. SIAM J. Comput. 40, 3 (June 2011), 848-877. DOI=10.1137/090751293. http://dx.doi.org/10.1137/090751293 Google ScholarDigital Library
- Assaf Naor, Oded Regev, Thomas Vidick 2012. Efficient Rounding for the Noncommutative Grothendieck Inequality, to appear in Proceedings of the 45nd ACM Symposium on Theory of Computing (STOC '13). arXiv:1210.7656v1.Google Scholar
Index Terms
- Proving grounds
Recommendations
Theorem Proving Modulo
AbstractDeduction modulo is a way to remove computational arguments from proofs by reasoning modulo a congruence on propositions. Such a technique, issued from automated theorem proving, is of general interest because it permits one to separate ...
Comments