pith. sign in

arxiv: 1907.08185 · v1 · pith:VFLDPZPBnew · submitted 2019-07-18 · 💻 cs.CC

Imperfect Gaps in Gap-ETH and PCPs

Mitali Bafna , Nikhil Vyas This is my paper

Pith reviewed 2026-05-24 19:08 UTC · model grok-4.3

classification 💻 cs.CC
keywords PCPperfect completenessGap-ETHrobust circuitthreshold gatesgap amplificationMAX-3SATsubexponential time
0
0 comments X

The pith

A PCP with imperfect completeness and constant gap converts to perfect completeness with only additive O(r) randomness and O(r) queries.

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

The paper establishes a transformation that turns any PCP with constant completeness-soundness gap into one with perfect completeness while increasing randomness by an additive constant and queries by an additive linear function of the original randomness. The conversion works by building a robust circuit from threshold gates. If correct, this means linear-sized PCPs for nondeterministic linear time can be made perfectly complete at the price of only an O(log n) increase in queries. The same techniques prove that Gap-ETH is equivalent in its imperfect-completeness and perfect-completeness forms, and they relate the randomized approximation times of the two versions by T2(n) ≤ T1(n (log log n)^{O(1)}).

Core claim

We show that PCP_{c,s}[r,q] ⊆ PCP_{1,1-Ω(1)}[r+O(1),q+O(r)] whenever c-s = Ω(1). The proof proceeds by constructing a robust circuit from threshold gates. This yields a method to convert imperfect completeness to perfect completeness in linear-sized PCPs for NTIME[O(n)] with an O(log n) additive loss in query complexity. We also show that Gap-3SAT with a constant gap not centered at 1 has a subexponential algorithm if and only if the perfectly complete version does, together with the fine-grained relation T2(n) ≤ T1(n (log log n)^{O(1)}) between their randomized approximation times.

What carries the argument

Robust circuit built from threshold gates that enforces perfect completeness while preserving a constant soundness gap.

If this is right

  • Linear-sized PCPs for NTIME[O(n)] become perfectly complete with only an O(log n) additive increase in queries.
  • Gap-ETH without the perfect-completeness requirement is equivalent to Gap-ETH with perfect completeness.
  • The randomized time T2 to approximate imperfect Gap-3SAT satisfies T2(n) ≤ T1(n (log log n)^{O(1)}) where T1 is the time for the perfect version.
  • The construction supplies a gap-amplification procedure that works even when the original PCP has imperfect completeness.

Where Pith is reading between the lines

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

  • PCP constructions may be easier if imperfect completeness is allowed first and then repaired by the robust-circuit step.
  • Hardness results proved for one version of Gap-ETH transfer immediately to the other version.
  • The same threshold-gate technique might extend to other proof-system parameters such as soundness or query locality.

Load-bearing premise

A robust circuit from threshold gates can be constructed for an arbitrary underlying PCP verifier that simultaneously achieves perfect completeness and keeps the constant soundness gap.

What would settle it

A concrete PCP verifier with constant gap for which no threshold-gate robust circuit achieves perfect completeness without either destroying the constant gap or exceeding the stated additive bounds on randomness and queries.

read the original abstract

We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfect completeness when the initial gap is a constant. In particular, we show that $\text{PCP}_{c,s}[r,q] \subseteq \text{PCP}_{1,1-\Omega(1)}[r+O(1),q+O(r)]$, for $c-s=\Omega(1)$. This implies that one can convert imperfect completeness to perfect in linear-sized PCPs for $NTIME[O(n)]$ with a $O(\log n)$ additive loss in the query complexity $q$. We show our result by constructing a "robust circuit" using threshold gates. These results are a gap amplification procedure for PCPs (when completeness is imperfect), analogous to questions studied in parallel repetition and pseudorandomness. We also investigate the time complexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the Gap-ETH conjecture without perfect completeness is equivalent to Gap-ETH with perfect completeness, i.e. we show that Gap-3SAT, where the gap is not around 1, has a subexponential algorithm, if and only if, Gap-3SAT with perfect completeness has subexponential algorithms. We also relate the time complexities of these two problems in a more fine-grained way, to show that $T_2(n) \leq T_1(n(\log\log n)^{O(1)})$, where $T_1(n),T_2(n)$ denote the randomized time-complexity of approximating MAX 3SAT with perfect and imperfect completeness, respectively.

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 / 1 minor

Summary. The manuscript claims that PCP_{c,s}[r,q] ⊆ PCP_{1,1-Ω(1)}[r+O(1),q+O(r)] whenever c-s=Ω(1), via an explicit construction of a 'robust circuit' from threshold gates that converts imperfect completeness to perfect completeness while preserving a constant soundness gap and adding only O(r) to randomness and queries. It further shows equivalence between Gap-ETH with and without perfect completeness (i.e., subexponential algorithms for imperfect-gap Gap-3SAT exist iff they exist for perfect-completeness Gap-3SAT) and the fine-grained relation T_2(n) ≤ T_1(n (log log n)^{O(1)}) between the randomized time complexities of the two approximation problems.

Significance. If the transformation holds, it supplies a general gap-amplification-style procedure for imperfect-completeness PCPs that yields perfect completeness in linear-sized PCPs for NTIME[O(n)] at the cost of only an O(log n) additive increase in query complexity. The equivalence result shows that the perfect-completeness restriction does not alter the subexponential hardness status of Gap-ETH. The paper supplies an explicit construction plus a reduction between two externally defined problems.

major comments (1)
  1. [Abstract / robust circuit construction] Abstract and the robust-circuit construction: the central inclusion rests on a single gadget (a robust circuit built from threshold gates) that is asserted to enforce acceptance probability exactly 1 on yes-instances while keeping soundness gap Ω(1) for arbitrary underlying verifiers. The manuscript invokes the gadget at high level but supplies no independent, self-contained argument verifying that the threshold-gate implementation simultaneously achieves both properties for every possible PCP verifier (including those arising from linear-size PCPs for NTIME[O(n)]). This is load-bearing for the general claim.
minor comments (1)
  1. The notation PCP_{c,s}[r,q] is introduced without an explicit reminder of the standard meaning of each parameter in the opening paragraphs; a one-sentence definition would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed reading and the constructive comment on the robust-circuit construction. We address the concern point-by-point below and agree that expanding the presentation will strengthen the paper.

read point-by-point responses

  1. Referee: [Abstract / robust circuit construction] Abstract and the robust-circuit construction: the central inclusion rests on a single gadget (a robust circuit built from threshold gates) that is asserted to enforce acceptance probability exactly 1 on yes-instances while keeping soundness gap Ω(1) for arbitrary underlying verifiers. The manuscript invokes the gadget at high level but supplies no independent, self-contained argument verifying that the threshold-gate implementation simultaneously achieves both properties for every possible PCP verifier (including those arising from linear-size PCPs for NTIME[O(n)]). This is load-bearing for the general claim.

    Authors: We agree that a more self-contained argument would improve clarity and verifiability. The construction is designed to work for arbitrary verifiers by using threshold gates to enforce a majority vote over multiple independent repetitions of the original verifier, which forces acceptance probability exactly 1 whenever the original completeness is at least c > s + Ω(1). However, the current write-up presents the gadget at a high level. In the revision we will insert a dedicated lemma (with a self-contained proof) that (i) explicitly defines the threshold-gate circuit, (ii) computes the exact acceptance probability on yes-instances for any underlying verifier, and (iii) shows that the soundness gap remains Ω(1) by a direct Chernoff-style calculation that holds independently of the original verifier’s structure. This lemma will also cover the linear-size PCPs for NTIME[O(n)] as a special case. We will therefore revise the manuscript to include this expanded argument. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit construction of robust circuit

full rationale

The paper derives the inclusion PCP_{c,s}[r,q] ⊆ PCP_{1,1-Ω(1)}[r+O(1),q+O(r)] via an explicit construction of a robust circuit from threshold gates. This is a direct, self-contained reduction between externally defined PCP classes with no fitted parameters, no self-definitional steps, and no load-bearing self-citations that reduce the claim to its inputs. The derivation stands on the construction itself rather than renaming or importing uniqueness from prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claims rest on the standard definition of PCP systems and the known existence of linear-size PCPs for NTIME[O(n)]; the new gadget is introduced without external evidence.

axioms (1)
  • domain assumption Standard definition of PCP_{c,s}[r,q] systems and the existence of linear-size PCPs for NTIME[O(n)]
    The implication for NTIME[O(n)] PCPs presupposes such PCPs exist with the parameters stated in prior literature.
invented entities (1)
  • robust circuit built from threshold gates no independent evidence
    purpose: To enforce perfect completeness while preserving constant soundness gap
    New gadget introduced by the paper; no independent evidence supplied outside the construction itself.

pith-pipeline@v0.9.0 · 5846 in / 1390 out tokens · 30397 ms · 2026-05-24T19:08:34.587696+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    (gap/s) eth hardness of SVP

    Divesh Aggarwal and Noah Stephens-Davidowitz. (gap/s) eth hardness of SVP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 , pages 228–238, 2018

    work page 2018

  2. [2]

    1998 , issue_date =

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Suda n, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM , 45(3):501–555, 1998. URL: https://doi.org/10.1145/278298.278306, doi:10.1145/278298.278306

    work page doi:10.1145/278298.278306 1998

  3. [3]

    Hardn ess amplification for entangled games via anchoring

    Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Hardn ess amplification for entangled games via anchoring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 303–316, 2017

    work page 2017

  4. [4]

    Free bit s, pcps, and nonapproximability-towards tight results

    Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bit s, pcps, and nonapproximability-towards tight results. SIAM J. Comput. , 27(3):804–915, 1998. URL: https://doi.org/10.1137/S0097539796302531, doi:10.1137/S0097539796302531

    work page doi:10.1137/s0097539796302531 1998

  5. [5]

    Con- stant rate pcps for circuit-sat with sublinear query comple xity

    Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir , and Henning Stichtenoth. Con- stant rate pcps for circuit-sat with sublinear query comple xity. In 54th Annual IEEE Sympo- sium on Foundations of Computer Science, FOCS 2013, 26-29 Octo ber, 2013, Berkeley, CA, USA, pages 320–329, 2013

    work page 2013

  6. [6]

    Short pcps with polylog q uery complexity

    Eli Ben-Sasson and Madhu Sudan. Short pcps with polylog q uery complexity. SIAM J. Comput. , 38(2):551–607, 2008. URL: https://doi.org/10.1137/050646445, doi:10.1137/050646445. 19

    work page doi:10.1137/050646445 2008

  7. [7]

    S., a nd Pasin Manurangsi

    Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., a nd Pasin Manurangsi. Parameterized intractability of even set and shortest vector problem from gap-eth. In 45th International Col- loquium on Automata, Languages, and Programming, ICALP 2018, J uly 9-13, 2018, Prague, Czech Republic, pages 17:1–17:15, 2018

    work page 2018

  8. [8]

    From gap-eth to fpt-i napproximability: Clique, dominating set, and more

    Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-eth to fpt-i napproximability: Clique, dominating set, and more. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 743–754, 2017

    work page 2017

  9. [9]

    Approximation resistance from pairwise ind ependent subgroups

    Siu On Chan. Approximation resistance from pairwise ind ependent subgroups. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, Jun e 1-4, 2013 , pages 447–456, 2013

    work page 2013

  10. [10]

    2007 , issue_date =

    Irit Dinur. The PCP theorem by gap amplification. J. ACM , 54(3):12, 2007. URL: https://doi.org/10.1145/1236457.1236459, doi:10.1145/1236457.1236459

    work page doi:10.1145/1236457.1236459 2007

  11. [11]

    Mildly exponential reduction from gap 3sat to polynomial-gap label-cover

    Irit Dinur. Mildly exponential reduction from gap 3sat to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC) , 23:128, 2016. URL: http://eccc.hpi-web.de/report/2016/128

    work page 2016

  12. [12]

    Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and M uli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 376–389, 2018

    work page 2018

  13. [13]

    Eth-hardness of appro ximating 2-csps and directed steiner network

    Irit Dinur and Pasin Manurangsi. Eth-hardness of appro ximating 2-csps and directed steiner network. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2 018, January 11-14, 2018, Cambridge, MA, USA , pages 36:1–36:20, 2018

    work page 2018

  14. [14]

    A chernoff bound for random walks on expan der graphs

    David Gillman. A chernoff bound for random walks on expan der graphs. SIAM J. Comput., 27(4):1203–1220, 1998. URL: https://doi.org/10.1137/S0097539794268765, doi:10.1137/S0097539794268765

    work page doi:10.1137/s0097539794268765 1998

  15. [15]

    A sample of samplers - A computational p erspective on sampling (sur- vey)

    Oded Goldreich. A sample of samplers - A computational p erspective on sampling (sur- vey). Electronic Colloquium on Computational Complexity (ECCC) , 4(20), 1997. URL: http://eccc.hpi-web.de/eccc-reports/1997/TR97-020/i ndex.html

    work page 1997

  16. [16]

    Tiny families of func tions with random properties: A quality-size trade-off for hashing

    Oded Goldreich and Avi Wigderson. Tiny families of func tions with random properties: A quality-size trade-off for hashing. Random Struct. Algorithms , 11(4):315–343, 1997

    work page 1997

  17. [17]

    The complexit y of making unique choices: Ap- proximating 1-in- k SAT

    Venkatesan Guruswami and Luca Trevisan. The complexit y of making unique choices: Ap- proximating 1-in- k SAT. In Approximation, Randomization and Combinatorial Optimiza- tion, Algorithms and Techniques, 8th International Worksho p on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9t h InternationalWorkshop on Randomizat...

    work page 2005

  18. [18]

    Some optimal inapproximability results

    Johan H ˚ astad. Some optimal inapproximability results. J. ACM , 48(4):798–859, 2001. URL: https://doi.org/10.1145/502090.502098, doi:10.1145/502090.502098. 20

    work page doi:10.1145/502090.502098 2001

  19. [19]

    On the compl exity of k-sat

    Russell Impagliazzo and Ramamohan Paturi. On the compl exity of k-sat. J. Com- put. Syst. Sci. , 62(2):367–375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727, doi:10.1006/jcss.2000.1727

    work page doi:10.1006/jcss.2000.1727 2001

  20. [20]

    Karp, Nicholas Pippenger, and Michael Sipse r

    Richard M. Karp, Nicholas Pippenger, and Michael Sipse r. A time-randomness tradeoff. In AMS Conference on Probabilistic Computational Complexity , 1982

    work page 1982

  21. [21]

    On the power of unique 2-prover 1-round ga mes

    Subhash Khot. On the power of unique 2-prover 1-round ga mes. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montr´ ea l, Qu´ ebec, Canada, pages 767–775, 2002

    work page 2002

  22. [22]

    A birthday re petition theorem and complexity of approximating dense csps

    Pasin Manurangsi and Prasad Raghavendra. A birthday re petition theorem and complexity of approximating dense csps. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland , pages 78:1–78:15, 2017

    work page 2017

  23. [23]

    Parallel repetition in projection games and a concentration bound

    Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM J. Comput. , 40(6):1871–1891, 2011. URL: https://doi.org/10.1137/080734042, doi:10.1137/080734042

    work page doi:10.1137/080734042 2011

  24. [24]

    A parallel repetition theorem

    Ran Raz. A parallel repetition theorem. SIAM J. Comput. , 27(3):763–803, 1998. URL: https://doi.org/10.1137/S0097539795280895, doi:10.1137/S0097539795280895. A Proof of Theorem 2.1 We first consider an expander sampler from Lemma 2.2. This is an expander graph G over N nodes, with the set family ES = ( Sv)v∈ [N ], where Sv = set of neighbors of v in G. To ...

    work page doi:10.1137/s0097539795280895 1998