pith. sign in

arxiv: 2404.07441 · v4 · pith:MZOEMO7Wnew · submitted 2024-04-11 · 💻 cs.CC · cs.DS

Near Optimal Alphabet-Soundness Tradeoff PCPs

Dor Minzer , Kai Zhe Zheng This is my paper

Pith reviewed 2026-05-24 02:41 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords PCPprojection gameshardness of approximationquadratic programming2-CSPinapproximabilityconnectivity problems
0
0 comments X

The pith

It is NP-hard to distinguish 2-prover projection games with value near 1 from value at most 1/q^{1-ε} for large power-of-two q.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for every ε greater than zero and all sufficiently large powers of two q, distinguishing 2-Prover-1-Round projection games whose value is at least 1-δ from those whose value is at most 1/q^{1-ε} is NP-hard. This improves the previous alphabet-to-soundness tradeoff for such games. The result is obtained by a reduction that maintains the projection property while pushing the soundness exponent closer to the information-theoretic limit. Because the hardness carries over to other problems via known reductions, it yields stronger inapproximability statements for quadratic programming and certain network-design tasks.

Core claim

For all ε>0, for sufficiently large q∈N 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-ε}.

What carries the argument

The 2-Prover-1-Round projection game, whose value is the maximum probability that two provers' answers satisfy a given projection constraint.

If this is right

  • It is NP-hard to approximate the value of Boolean Quadratic Programs within a factor of (log n)^{1-o(1)} under quasi-polynomial time reductions.
  • Under randomized reductions, for sufficiently large d it is NP-hard to approximate the value of 2-CSPs with maximum degree d within a factor of (1-o(1))d/2.
  • Improved NP-hardness results hold for the Rooted k-Connectivity Problem, the Vertex-Connectivity Survivable Network Design Problem, and the Vertex-Connectivity k-Route Cut Problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Extending the construction to all large q rather than only powers of two would remove the remaining technical restriction on alphabet size.
  • The same reduction technique could be tested on other base hardness assumptions to obtain polynomial-time rather than quasi-polynomial reductions for quadratic programming.
  • The near-optimality suggests that further improvement in the exponent would require qualitatively new ideas beyond current Fourier-analytic or algebraic methods.

Load-bearing premise

The reduction from a known hard problem can preserve the projection property while achieving the improved soundness exponent for arbitrarily large powers of two.

What would settle it

A polynomial-time algorithm that distinguishes 2-prover projection games of value at least 1-δ from those of value at most 1/q^{1-ε} for some large power-of-two q and small ε would falsify the claim.

read the original abstract

We show that for all $\varepsilon>0$, for sufficiently large $q\in\mathbb{N}$ power of $2$, for all $\delta>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-\delta$, or value at most $1/q^{1-\varepsilon}$. This establishes a nearly optimal alphabet-to-soundness tradeoff for $2$-query PCPs with alphabet size $q$, improving upon a result of [Chan, Journal of the 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 within factor $(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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript claims that for every ε>0 and all sufficiently large q=2^k, for every δ>0, it is NP-hard to distinguish whether a 2-Prover-1-Round projection game over alphabet size q has value at least 1-δ or at most 1/q^{1-ε}. The result improves the soundness exponent over Chan (JACM 2016) while preserving the projection property and yields improved hardness for Boolean quadratic programming (within (log n)^{1-o(1)}), bounded-degree 2-CSPs (within (1-o(1))d/2), and several connectivity problems via reductions from Laekhanukit and Manurangsi.

Significance. If correct, the result is a meaningful advance in PCP theory: it nearly closes the alphabet-soundness gap for 2-query projection games and produces concrete improvements in three application domains, coming close to the best known algorithmic guarantees for quadratic programming. The construction appears to rely on a new reduction that avoids the extra losses present in prior work.

major comments (1)
  1. [§4] §4 (Reduction and Projection Preservation): The central claim requires that the new reduction from a hard Label-Cover or projection-game instance produces only projection constraints while attaining soundness 1/q^{1-ε} for arbitrary ε. The manuscript must explicitly verify that every constraint remains a function of one prover's answer to the other's and that the Fourier/algebraic analysis incurs no additional loss that would cap the exponent below 1-ε for large powers of two.
minor comments (2)
  1. [Abstract] The abstract and introduction should state the precise dependence of q on ε (i.e., how large q must be) rather than only “sufficiently large.”
  2. [§5] Notation for the value of the game and the projection function should be introduced once and used consistently in the applications section.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive assessment of the result's significance and for identifying the key point requiring clarification in Section 4. We address the major comment below and are prepared to revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§4] §4 (Reduction and Projection Preservation): The central claim requires that the new reduction from a hard Label-Cover or projection-game instance produces only projection constraints while attaining soundness 1/q^{1-ε} for arbitrary ε. The manuscript must explicitly verify that every constraint remains a function of one prover's answer to the other's and that the Fourier/algebraic analysis incurs no additional loss that would cap the exponent below 1-ε for large powers of two.

    Authors: Section 4 constructs the reduction explicitly from a Label-Cover instance and proves (Lemma 4.3 and Claim 4.5) that every output constraint is a projection: the second prover's answer is a deterministic function of the first prover's answer on the shared edge. The soundness analysis in Section 4.3 uses the Fourier decomposition over the power-of-two alphabet and applies the invariance principle together with the noise operator; the only losses are the standard (1-ε) factors from the base PCP and the ε-slack in the influence bounds, which are controlled uniformly for all sufficiently large q=2^k. No additional multiplicative loss appears that would force the exponent below 1-ε. We will add a short dedicated paragraph immediately after the soundness theorem statement that restates these two facts with forward references to the relevant lemmas, making the verification fully explicit. revision: yes

Circularity Check

0 steps flagged

New reduction from established hardness yields improved soundness exponent

full rationale

The paper derives its main hardness statement for 2P1R projection games via an explicit new reduction that starts from a known hard instance (building on Chan 2016) and produces a new instance while preserving the projection property and achieving the 1/q^{1-ε} soundness bound. No equation, parameter fit, or self-citation is shown to make the output equivalent to the input by construction; the cited prior result is by different authors and supplies an independent starting hardness assumption rather than a load-bearing uniqueness theorem. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard complexity assumptions (P≠NP and validity of prior PCP theorems) and the existence of suitable algebraic or Fourier-analytic reductions that preserve projection games; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Standard assumption that P ≠ NP and that prior PCP constructions (e.g., those underlying Chan 2016) remain valid when composed with the new reduction.
    The NP-hardness statement is conditional on these background results in complexity theory.

pith-pipeline@v0.9.0 · 5913 in / 1296 out tokens · 28937 ms · 2026-05-24T02:41:09.306490+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    That is,QandWsatisfydim(Q)+codim(W) = rand there exists linearg Q,W :W→F q such that Pr L∈Grass(n,2ℓ) [gQ,W |L = eT1[L]|Q⊆L⊆W]⩾ε ′ :=q −2(1−1000δ2)ℓ

    LetQ⊂Wbe subspaces guaranteed by Theorem 5.1. That is,QandWsatisfydim(Q)+codim(W) = rand there exists linearg Q,W :W→F q such that Pr L∈Grass(n,2ℓ) [gQ,W |L = eT1[L]|Q⊆L⊆W]⩾ε ′ :=q −2(1−1000δ2)ℓ

    work page

  2. [2]

    SetX ← − X ∪ {L|Q⊆L⊆W}

    work page

  3. [3]

    We have the following claim regarding the re-assignment phase

    For eachL∈ Xindependently, choose eT1[L]uniformly among all linear functions onL. We have the following claim regarding the re-assignment phase. Claim B.1.With probability at least1−e −Ω(qℓn) over the random assignmenteT1, for every pair of subspaces Q⊂Wsuch thatdim(Q)+codim(W) =randµ Q,W (X)⩾q −2ℓ, and every linear functiong Q,W :W− → Fq, we have Pr L∈X,...

    work page

  4. [4]

    Choose(X, σ)with probability proportional to|W X,σ|

    work page

  5. [5]

    ChooseW i ∈ W X,σ uniformly

    work page

  6. [6]

    NWX,σ(L)⩽0.9 E L∈LX [NWX,σ(L)] # = Pr L∈LX

    Choose a2ℓ-dimensional subspaceLuniformly conditioned onX⊆L⊆W i. Notice that the distribution of(W i, L)above is equivalent to that of choosingW i ∈ Wuniformly and L⊂W i uniformly. Moreover,f i|L ≡T[L]only ifL∈ L X,σ, asf i andT[L]must agree onX⊆Lin order to agree onL. Therefore, E X,σ [qX,σ]⩾Pr Wi∈W,L⊆W i [fi|L ≡T[L]]⩾C⩾ 1 q2(1−ξ)ℓ .(43) On the other han...

    work page

  7. [7]

    Now letW ⋆ [A,B] ={W ⋆ i | ∃W i ∈ W X,σ s.tA⊕W ⋆ i =W i ∩B}

    We next recall a few notations: for a zoom-inAand zoom-outBsuch thatX⊆A⊆B⊆V ′, we writeV ′ =A⊕V 0 andB=A⊕V ⋆, whereV ⋆ ⊆V 0. Now letW ⋆ [A,B] ={W ⋆ i | ∃W i ∈ W X,σ s.tA⊕W ⋆ i =W i ∩B}. It is clear that eachW ⋆ i ∈ W ⋆ [A,B] is contained inside of someW i ∈ W X,σ, so for eachW ⋆ i , we may define f ⋆ i ≡f i|W ⋆ i . If there are multiple suchi, we choose o...

    work page

  8. [8]

    The setL ⋆ is(1, q δ2ℓη)-pseudo-random

    work page

  9. [9]

    EachW ⋆ i has codimensions⩽rinside ofV ⋆ andW ⋆ is4-generic, with respect toV ⋆

    work page

  10. [10]

    The size ofW ⋆ satisfies m2 ·q −10s/δ2 2 ⩽m 3 ⩽m 2

    work page

  11. [11]

    For everyL∈ L ⋆, choosingW ⋆ i ∈ W ⋆ uniformly such thatW ⋆ i ⊇L, we have Pr W ⋆ i ⊇L,W ⋆ i ∈W ⋆ [fi|L ̸≡T ℓ′[L]]⩽14γ

    work page

  12. [12]

    The following result finds the zoom-in and zoom-out pair as required for Lemma 8.3, modulo a few minor alterations

    For everyL∈ L ⋆, 0.8·p 1 ·m 3 ⩽N W ⋆(L)⩽1.2·p 1 ·m 3, whereN W ⋆(L)is as defined in(13), and p1 = Pr L∈Grassq(V ⋆,ℓ′) [L⊆W], for an arbitraryW⊆V ⋆ of codimensions. The following result finds the zoom-in and zoom-out pair as required for Lemma 8.3, modulo a few minor alterations. Lemma E.3.We can find a zoom-inAand a zoom-outBsuch thatX⊆A⊆B⊆V ′, such that ...

    work page

  13. [13]

    Now do the following

    work page

  14. [14]

    Seti= 0, and initializeA 0,L 0, B0, η0 as above

    work page

  15. [15]

    IfL i is(1, q δ2ℓηi)-pseudo-random inside ofZoom[A i, Bi], then stop

    work page

  16. [16]

    Otherwise, there existA⊆Bsuch that,A i ⊆A⊆B⊆B i,dim(A) + codim(B) = dim(A i) + codim(Bi) + 1, andµ [A,B](Li)⩾q δ2ℓηi

    work page

  17. [17]

    SetA i+1 :=A,B i+1 :=B,L i+1 :=L i ∩Zoom[A i+1, Bi+1], and letη i+1 :=µ [Ai+1,Bi+1](Li+1)

    work page

  18. [18]

    11By(1, q δ2ℓη)-pseudo-random inZoom[A, B]we mean thatL ′ does not increase its fractional size toq δ2ℓηwhen restricted to any zoom-in containingAor any zoom-out contained inB

    Incrementiby1and return to step2. 11By(1, q δ2ℓη)-pseudo-random inZoom[A, B]we mean thatL ′ does not increase its fractional size toq δ2ℓηwhen restricted to any zoom-in containingAor any zoom-out contained inB. 94 Suppose this process terminates on iterationj. We claim that takingL ′ =L j,A=A j, andB=B j, satisfies the requirements of the lemma. First, no...

    work page

  19. [19]

    For eachz∈Z, the number ofi, jsuch thatµ [z,W ⋆ i ∩W ⋆ j ](L⋆)⩽ 4 5 ηis at most 106q4sℓ η2 m3

    work page

  20. [20]

    Proof.Fix a pointz∈Z, letF z be the restriction ofFto the zoom-in ofz, whereF(x 1,

    for everyW ⋆ i , W ⋆ j ∈ W ⋆, we haveµ W ⋆ i ∩W ⋆ j (Z)⩾0.9µ(Z). Proof.Fix a pointz∈Z, letF z be the restriction ofFto the zoom-in ofz, whereF(x 1, . . . , xℓ′) = 1if span(x1, . . . , xℓ′)∈ L ⋆ and0otherwise. Letη ′ =µ z(L⋆). Sincez∈Z, we haveη ′ ∈[0.9η,1.1η]. Note that ifi, jsatisfyµ [z,W ⋆ i ∩W ⋆ j ](L⋆)⩽ 4 5 η, then (usingη ′ ∈[0.9η,1.1η]) µ[z,W ⋆ i ∩W...

    work page