Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Near Optimal Alphabet-Soundness Tradeoff PCPs

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ أكثر حفظ في قائمتي
  • معلومة اضافية
    • Publisher Information:
      Association for Computing Machinery STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing 2024-07-18T15:49:19Z 2024-07-18T15:49:19Z 2024-06-10 2024-07-01T07:46:38Z
    • نبذة مختصرة :
      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.
    • الموضوع:
      Article; http://purl.org/eprint/type/JournalArticle
    • Availability:
      Open access content. Open access content
      Creative Commons Attribution
      https://creativecommons.org/licenses/by/4.0
      The author(s)
    • Note:
      application/pdf
      English
    • Other Numbers:
      MYG oai:dspace.mit.edu:1721.1/155706
      979-8-4007-0383-6
      Minzer, Dor and Zheng, Kai Zhe. 2024. "Near Optimal Alphabet-Soundness Tradeoff PCPs."
      PUBLISHER_CC
      1469875827
    • Contributing Source:
      MASSACHUSETTS INST OF TECHNOL LIBRS
      From OAIster®, provided by the OCLC Cooperative.
    • الرقم المعرف:
      edsoai.on1469875827
HoldingsOnline