Loading...
Please wait, while we are loading the content...
Similar Documents
Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems
| Content Provider | Semantic Scholar |
|---|---|
| Author | Cleve, Richard Gavinsky, Dmitry Jain, Rahul |
| Copyright Year | 2007 |
| Abstract | We show that, for any language in NP, there is an entanglement-resistant constant-bit two-prover interactive proof system with a constant completeness vs. soundness gap. The previously proposed classical two-prover constant-bit interactive proof systems are known not to be entanglement-resistant. This is currently the strongest expressive power of any known constant-bit answer multi-prover interactive proof system that achieves a constant gap. Our result is based on an "oracularizing" property of certain private information retrieval systems, which may be of independent interest. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://arxiv.org/pdf/0707.1729v1.pdf |
| Alternate Webpage(s) | http://users.math.cas.cz/~gavinsky/papers/e-rips.pdf |
| Alternate Webpage(s) | http://arxiv.org/pdf/0707.1729v1.pdf |
| Alternate Webpage(s) | http://www.cs.uwaterloo.ca/~rjain/allfiles/NpXorMip-july8.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
