Near Optimal Alphabet-Soundness Tradeoff PCPs
We show that for all > 0, for su ciently large prime power ∈ N, for all > 0, it is NP-hard to distinguish whether a 2-Prover1-Round projection game with alphabet size has value at least 1 − , or value at most 1/ 1− . This establishes a nearly optimal alphabet-to-soundness tradeo for...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155706 |