EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Near Optimal Alphabet-Soundness Tradeoff PCPs

Dor Minzer, Kai Zhe Zheng

Journal of the ACM · 31.08.2026 · 73 (4) · 1-98

DOI: 10.1145/3816427 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 11.08.2026. Verfasst von Dor Minzer und 1 weiteren Autor:innen. Die Arbeit nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF CCF, NSF CAREER, NSF GRFP.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We show that for all ɛ > 0, for sufficiently large q ∈ ℕ that is a power of 2, for all δ > 0, it is NP-hard to distinguish whether a given 2-Prover-1-Round projection game with alphabet size q has value at least 1-δ, or value at most 1/ q 1-ɛ . This establishes a nearly optimal alphabet-to-soundness tradeoff for 2-query PCPs with alphabet size q , improving upon a result of [Chan, J. ACM 2016]. Our result has the following implications: (1) Near optimal hardness for Quadratic Programming: it is NP-hard to approximate the value of a given Boolean Quadratic Program within factor (log n ) 1 - o (1) under quasi-polynomial time reductions. This improves upon a result of [Khot, Safra, ToC 2013] and nearly matches the performance of the best known algorithms due to [Megretski, IWOTA 2000], [Nemirovski, Roos, Terlaky, Mathematical Programming 1999] and [Charikar, Wirth, FOCS 2004] that achieve O (log n ) approximation ratio. (2) Bounded degree 2-CSPs: under randomized reductions, for sufficiently large d > 0, it is NP-hard to approximate the value of 2-CSPs in which each variable appears in at most d constraints to within a factor of (1- o (1)) \(\frac{d}{2}\) , improving upon a result of [Lee, Manurangsi, ITCS 2024]. (3) Improved hardness results for connectivity problems: using results of [Laekhanukit, SODA 2014] and [Manurangsi, Inf. Process. Lett., 2019], we deduce improved hardness results for the Rooted k -Connectivity Problem, the Vertex-Connectivity Survivable Network Design Problem and the Vertex-Connectivity k -Route Cut Problem.

Förderung

  • NSF CCF
  • NSF CAREER
  • NSF GRFP

Zitieren

APA

Minzer, D., & Zheng, K. Z. (2026). Near Optimal Alphabet-Soundness Tradeoff PCPs. Journal of the ACM, 73(4), 1-98. https://doi.org/10.1145/3816427

Vancouver

Minzer D, Zheng KZ. Near Optimal Alphabet-Soundness Tradeoff PCPs. Journal of the ACM. 2026;73(4):1-98. doi:10.1145/3816427

BibTeX
@article{Minzer2026,
  author = {Minzer, Dor and Zheng, Kai Zhe},
  title = {Near Optimal Alphabet-Soundness Tradeoff PCPs},
  journal = {Journal of the ACM},
  year = {2026},
  volume = {73},
  number = {4},
  pages = {1--98},
  doi = {10.1145/3816427}
}
Kostenlos starten →