Near Optimal Alphabet-Soundness Tradeoff PCPs

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...

Full description

Bibliographic Details
Main Authors: Minzer, Dor, Zheng, Kai Zhe
Other Authors: Massachusetts Institute of Technology. Department of Mathematics
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

Similar Items

Similar Items