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: | , |
|---|---|
| Other 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 |
| _version_ | 1824458479375482880 |
|---|---|
| author | Minzer, Dor Zheng, Kai Zhe |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Minzer, Dor Zheng, Kai Zhe |
| author_sort | Minzer, Dor |
| collection | MIT |
| description | 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 2-query PCPs with alphabet
size , improving upon a result of [Chan 2016]. Our result has the
following implications:
(1) Near optimal hardness for Quadratic Programming: it is NPhard to approximate the value of a given Boolean Quadratic
Program within factor (log)
1− (1) under quasi-polynomial
time reductions. This result improves a result of [Khot-Safra
2013] and nearly matches the performance of the best known
approximation algorithm [Megrestki 2001, Nemirovski-RoosTerlaky 1999 Charikar-Wirth 2004] that achieves a factor of
(log).
(2) Bounded degree 2-CSP’s: under randomized reductions, for
su ciently large > 0, it is NP-hard to approximate the
value of 2-CSPs in which each variable appears in at most
constraints within factor (1 − (1))
2
, improving upon a
recent result of [Lee-Manurangsi 2023].
(3) Improved hardness results for connectivity problems: using
results of [Laekhanukit 2014] and [Manurangsi 2019], we deduce improved hardness results for the Rooted -Connectivity
Problem, the Vertex-Connectivity Survivable Network Design Problem and the Vertex-Connectivity -Route Cut Problem. |
| first_indexed | 2024-09-23T17:14:29Z |
| format | Article |
| id | mit-1721.1/155706 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:26:33Z |
| publishDate | 2024 |
| publisher | Association for Computing Machinery STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing |
| record_format | dspace |
| spelling | mit-1721.1/1557062025-01-01T04:07:08Z Near Optimal Alphabet-Soundness Tradeoff PCPs Minzer, Dor Zheng, Kai Zhe Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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 2-query PCPs with alphabet size , improving upon a result of [Chan 2016]. Our result has the following implications: (1) Near optimal hardness for Quadratic Programming: it is NPhard to approximate the value of a given Boolean Quadratic Program within factor (log) 1− (1) under quasi-polynomial time reductions. This result improves a result of [Khot-Safra 2013] and nearly matches the performance of the best known approximation algorithm [Megrestki 2001, Nemirovski-RoosTerlaky 1999 Charikar-Wirth 2004] that achieves a factor of (log). (2) Bounded degree 2-CSP’s: under randomized reductions, for su ciently large > 0, it is NP-hard to approximate the value of 2-CSPs in which each variable appears in at most constraints within factor (1 − (1)) 2 , improving upon a recent result of [Lee-Manurangsi 2023]. (3) Improved hardness results for connectivity problems: using results of [Laekhanukit 2014] and [Manurangsi 2019], we deduce improved hardness results for the Rooted -Connectivity Problem, the Vertex-Connectivity Survivable Network Design Problem and the Vertex-Connectivity -Route Cut Problem. 2024-07-18T15:49:19Z 2024-07-18T15:49:19Z 2024-06-10 2024-07-01T07:46:38Z Article http://purl.org/eprint/type/JournalArticle 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155706 Minzer, Dor and Zheng, Kai Zhe. 2024. "Near Optimal Alphabet-Soundness Tradeoff PCPs." PUBLISHER_CC en 10.1145/3618260.3649606 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf Association for Computing Machinery STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing Association for Computing Machinery |
| spellingShingle | Minzer, Dor Zheng, Kai Zhe Near Optimal Alphabet-Soundness Tradeoff PCPs |
| title | Near Optimal Alphabet-Soundness Tradeoff PCPs |
| title_full | Near Optimal Alphabet-Soundness Tradeoff PCPs |
| title_fullStr | Near Optimal Alphabet-Soundness Tradeoff PCPs |
| title_full_unstemmed | Near Optimal Alphabet-Soundness Tradeoff PCPs |
| title_short | Near Optimal Alphabet-Soundness Tradeoff PCPs |
| title_sort | near optimal alphabet soundness tradeoff pcps |
| url | https://hdl.handle.net/1721.1/155706 |
| work_keys_str_mv | AT minzerdor nearoptimalalphabetsoundnesstradeoffpcps AT zhengkaizhe nearoptimalalphabetsoundnesstradeoffpcps |