Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Any q-query PCPP with soundness 1−ε gives PSPACE-hardness for (q+1)-ary CSP reconfiguration.

desk verdict Clean parallelization trick, but the main theorem leans on a theorem the paper never proves, so the headline result is only as solid as that attribution. read the letter →

arxiv 2507.01192 v1 pith:KNGKN6KH submitted 2025-07-01 cs.CC

Venkatesan Guruswami , Xuandi Ren , Kewen Wu This is my paper · ORCID
classification cs.CC MSC 68Q1768Q15
keywords reconfigurationCSPPCPPPSPACE-hardnesssoundnessgapquerycomplexityparallelizationinapproximability
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that the soundness gap of approximate CSP reconfiguration can match the soundness gap of the underlying PCPP, at the price of only one extra query. Concretely, if every Boolean circuit has a q-query PCPP with proximity parameter δ, soundness 1−ε, and O(log n) randomness, then for some constant alphabet Σ the problem Gap_{1,1−ε} (q+1)-CSPΣ Reconfiguration is PSPACE-hard. The proof stacks several PCPPs into layers and checks them in parallel through the same query pattern, improving the previous bound of 1−ε/4 to the full 1−ε. This makes the query-versus-soundness tradeoff of reconfiguration essentially identical to that of PCPPs, and puts the construction of explicit PCPPs at the center of future quantitative improvements.

What carries the argument

The load-bearing object is the t-parallel PCPP construction. For constant t, a set of t PCPP verifiers is parallelizable when, for every random string, all t verifiers query the same q locations in their respective input–proof composites. The paper stacks the t inputs as rows of a t×(n+m) table, adds one selector variable v taking values in [t], and for each random string writes a single (q+1)-ary constraint that reads the shared q-tuple of columns and accepts exactly when the PCPP verifier selected by v accepts on that row's values. This gadget converts t separate PCPP checks into one CSP constraint set while preserving completeness (each accepted row can be changed independently) and soundness (if every row is rejected with probability at most κ, the CSP value is at most κ).

What would settle it

Take any q-query PCPP satisfying the stated hypothesis, run the paper's reduction, and brute-force the resulting (q+1)-ary CSP reconfiguration instance on small circuits: if a sequential walk of value at least 1−ε exists in the No case, or if the Yes-case walk fails to exist, then the completeness or soundness lemma is false.

Watch

Extended reading notes

Core claim

The central claim is a quantitative transfer theorem: the hardness threshold for CSP reconfiguration can inherit the exact soundness of a PCPP. For a fixed constant δ>0, if every Boolean circuit of size n admits a q-query PCPP with proximity parameter δ, soundness 1−ε, and randomness O(log n), then there is a constant-sized alphabet Σ such that Gap_{1,1−ε} (q+1)-CSPΣ Reconfiguration is PSPACE-hard. Earlier work of [KM24] gave only soundness 1−ε/4 with the same extra query; the paper removes this constant loss by parallelizing four PCPP checks on stacked copies of the assignment and proof strings. The result is a clean statement that up to an additional arity, the soundness gap of reconfiguration equals the soundness gap of PCPPs.

Load-bearing premise

The main theorem rests on Theorem 12, which the paper states as 'Implicit in [KM24]' and does not prove; if that intermediate 4-parallel PCPP hardness statement is not actually established by the cited work, the chain from PCPPs to Theorem 2 breaks.

Editorial extensions

If this is right

  • Under the stated PCPP hypothesis, Gap_{1,1−ε} (q+1)-CSPΣ Reconfiguration is PSPACE-hard, with only the single selector variable as overhead.
  • By combining with the arity-to-soundness tradeoff of [Ohs24b], the same hypothesis yields PSPACE-hardness of Gap_{1,1−ε/(q+1)} 2-CSPΣ Reconfiguration.
  • Any future construction of explicit PCPPs with small constant query complexity and low soundness would immediately improve the currently known soundness threshold near 0.9942 for 2-CSP reconfiguration.
  • The reduction works for constant-sized proof alphabets beyond binary, producing a final CSP alphabet that is the t-th power of the proof alphabet.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same parallelization scheme likely applies to the multi-stage verifier of [HO24] if its query sets align per randomness, offering an independent route to the same soundness transfer.
  • If the stated-implicit Theorem 12 is fully proved, the reconfiguration-hardness program reduces to constructing PCPPs with good query–soundness tradeoffs, linking RIH directly to open PCP questions.
  • The abstraction of parallelizable verifiers suggests that any structured family of PCPPs sharing query patterns can be plugged into this reduction without redoing the CSP construction.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the connection between the Reconfiguration Inapproximability Hypothesis (RIH) and probabilistically checkable proofs of proximity (PCPP). It proposes a "parallelization" construction that stacks several PCPP verifiers into layers and converts them into a single (q+1)-CSP instance over a constant-sized alphabet. The central claim, Theorem 2, states that, assuming a family of q-query PCPPs with proximity parameter δ, soundness 1−ε, and O(log n) randomness, the problem Gap_{1,1−ε} (q+1)-CSP_Σ Reconfiguration is PSPACE-hard. Corollary 3 combines this with a lemma from Ohsaka to obtain a soundness gap of 1−ε/(q+1) for 2-CSP Reconfiguration. The main technical section proves Theorem 8, a single-assignment completeness/soundness statement for the parallel construction, and Corollary 10, which reduces a new problem called Gap t-Parallel q-PCPP Reconfiguration to Gap CSP Reconfiguration. However, the paper relies on Theorem 12, stated as "Implicit in [KM24]" and not proved, for the PSPACE-hardness of the base 4-Parallel q-PCPP Reconfiguration problem. This attribution is load-bearing because Theorem 2 is exactly the conjunction of Theorem 12 and Corollary 10.

Significance. If the main theorem and its cited cornerstone Theorem 12 are correct, the paper provides a clean and quantitatively strong connection between PCPP soundness and RIH, eliminating the factor-1/4 loss present in the earlier KM24-style argument. The parallelization idea, imported from parameterized inapproximability, is plausible and could be useful for future gap-amplification results. The claimed improvement from soundness 1−ε/4 to 1−ε is significant and directly relevant to the goal of reducing the 0.9942 soundness bound for Gap 2-CSP Reconfiguration, although the paper correctly notes that explicit PCPP constructions with the required parameters are not currently known. The exposition is compact and the single-assignment construction (Theorem 8) is simple enough to verify, but as submitted the paper does not supply a proof of the hardness of the base t-Parallel problem and glosses over a key issue in the reconfiguration reduction. These gaps are repairable, but they are load-bearing for the central claim.

major comments (3)
  1. [Section 3.2, Theorem 12] Theorem 12 is asserted as "Implicit in [KM24]" without proof or a lemma-level derivation. This is load-bearing: Theorem 2 is exactly Theorem 12 combined with Corollary 10. The paper's own review of KM24 in Section 3.1 derives only the weaker statement that Gap_{1,1−ε/4} (q+1)-CSP Reconfiguration is PSPACE-hard, where the factor 1/4 comes from letting three of four verifiers pass for free. Theorem 12 instead requires PSPACE-hardness of Gap_{1,1−ε} 4-Parallel q-PCPP_Σ Reconfiguration, a formulation with a different reconfiguration step (changing one column of t parallel bits) and an existential acceptance condition. The authors must either locate Theorem 12 verbatim in KM24 with its proof, or prove it here. Without this, the main implication is conditional on an unverified attribution.
  2. [Theorem 8, completeness] The completeness statement of Theorem 8 is false as written. For a full assignment ψ of Π, the value val_Π(ψ) equals the acceptance probability of the single verifier V_{ψ(v)}, because the constraint for each random string checks only that verifier. If some i different from ψ(v) satisfies V_i(ψ(x(i))∘ψ(π(i))) with probability 1 while V_{ψ(v)} has low acceptance probability, the conclusion val_Π(ψ)=1 does not follow. The statement should be repaired by quantifying over v, e.g., "if ψ(v)=i and V_i accepts with probability 1, then val_Π(ψ)=1," or by phrasing the result as an extension property: for every assignment to x and π and every i accepted with probability 1, there is an assignment to v that makes the full CSP assignment have value 1.
  3. [Corollary 10] The reduction from Gap t-Parallel q-PCPP Reconfiguration to Gap (q+1)-CSP Reconfiguration is not justified in the paper. In the YES case of the t-Parallel problem, each assignment ψ has some witness i (possibly depending on ψ) such that V_i accepts with probability at least c. The CSP reduction must add the variable v, but a single reconfiguration step in the CSP instance changes at most one coordinate, so it cannot simultaneously change v and a column of x or π. If the witness changes from i to i' between two adjacent t-Parallel assignments, inserting an intermediate step with (i',ψ) or (i,ψ') may violate completeness because the corresponding verifier need not accept that assignment. The paper needs to supply an argument showing how to schedule the change of v (for example, by keeping v fixed and updating auxiliary proofs while the old verifier remains active, or by proving that the hard instances from Theorem 12 admit a sequence with a single uniformly valid witness).
minor comments (4)
  1. [Definition 4 and Definition 7] The PCPP definition does not explicitly state that the verifier is non-adaptive. This matters for Definition 7, where "the same set of q locations" for each random string presumes the query locations are determined before reading any answers.
  2. [Definition 9] The notation Gap_{c,s} t-Parallel q-PCPP_Σ Reconfiguration uses the subscript Σ, but the definition quantifies assignments into {0,1}^t and never refers to Σ; please either remove the subscript or define the proof alphabet explicitly.
  3. [Section 3.2, paragraph after Theorem 8] The sentence "We treat {0,1}^t, the alphabet of v, as a super-set of [t]" should specify the encoding of the t values as elements of {0,1}^t, since the constraint satisfaction condition depends on this identification.
  4. [Corollary 3] The derivation of Corollary 3 appeals to [Ohs24b, Lemma 5.4] without stating the lemma; including its statement would make the paper more self-contained and clarify the exact arity-versus-soundness trade-off.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the paper's own reduction is self-contained, and the main theorem is a conditional implication resting on the external result of [KM24], which is a dependency rather than a circular step.

full rationale

The derivation chain is not circular. Theorem 8 provides a self-contained polynomial-time parallelization construction with completeness and soundness proven in Section 3.2, and Corollary 10 directly reduces t-Parallel q-PCPP Reconfiguration to Gap CSP Reconfiguration. The main Theorem 2 combines this with Theorem 12, stated as 'Implicit in [KM24]'. This is reliance on an independent prior result, not a self-citation chain, and not a renaming of the paper's own assumptions. The concern that Theorem 12 is asserted without a proof is a correctness or completeness risk, not circularity. The self-citations [LRSW23, GLR+24b, GLR+24a] only serve as inspiration for the parallelization idea and are not load-bearing: the formal proof does not depend on them. No fitted parameter is renamed as a prediction, and no equation is defined in terms of the target result.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted parameters or new physical or mathematical entities. Its central claim is conditional on an assumed PCPP with specified parameters; that assumption is a theorem hypothesis, not a free parameter. The main load-bearing unproved input is Theorem 12 attributed to KM24.

assumptions (4)
  • domain assumption PSPACE-hardness of Gap_{1,1} 2-CSP_Sigma Reconfiguration for constant Sigma
    Used as the starting point of the reduction in Section 3.1, citing GKMP09 and Ohs23.
  • standard math Existence and efficiency of binary error correcting codes C: {0,1}^{n log|Sigma|} to {0,1}^m with constant relative distance
    Used to encode assignments in the KM24 construction; standard coding theory.
  • domain assumption Theorem 12: Gap_{1,1-epsilon} 4-Parallel q-PCPP_Sigma Reconfiguration is PSPACE-hard, attributed as implicit in KM24
    Stated without proof in Section 3.2; load-bearing for Theorem 2.
  • standard math Standard PSPACE brute-force upper bound to establish completeness
    Used in footnote 2; PSPACE membership for Gap CSP Reconfiguration.

how reviews work

0 comments
Cite this review

Pith. "Pith review of PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs." pith.science (2026). https://pith.science/paper/KNGKN6KH

@misc{pith2026250701192,
  author       = {Pith},
  title        = {Pith review of: PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KNGKN6KH}},
  note         = {Machine review of arXiv:2507.01192}
}
read the original abstract

The Reconfiguration Inapproximability Hypothesis (RIH), recently established by Hirahara-Ohsaka (STOC'24) and Karthik-Manurangsi (ECCC'24), studies the hardness of reconfiguring one solution into another in constraint satisfaction problems (CSP) when restricted to approximate intermediate solutions. In this work, we make a tighter connection between RIH's soundness gap and that of probabilistically checkable proofs of proximity (PCPP). Consequently, we achieve an improved trade-off between soundness and query complexity in Gap CSP Reconfiguration. Our approach leverages a parallelization framework, which also appears in some recent parameterized inapproximability results.

Figures

Figures reproduced from arXiv: 2507.01192 by the authors.

Figure 1
Figure 1. An illustration of the t-Parallel PCPP construction (t = 4). Definition 9 (Gap t-Parallel q-PCPPΣ Reconfiguration). For any constant t ≥ 1 and any 0 ≤ s ≤ c ≤ 1, Gapc,s t-Parallel q-PCPP Reconfiguration asks, for t parallelizable (n, m,r, q)-PCPPs V1, . . . , Vt and their two assignments ψ ini , ψ tar : (x ∪ π) → {0, 1} t , to distinguish between the following two cases: • YES CASE. There is a reconfiguration sequen… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration

    cs.CC 2026-07 accept novelty 7.5 of 10

    Maxmin q-CSP Reconfiguration is PSPACE-hard to approximate within 1/2^{q-1}+ε, while a (1/2^{q-1}-ε)-factor is in NP under perfect completeness, optimally under NP≠PSPACE.

Reference graph

Works this paper leans on

22 extracted references · 21 canonical work pages · cited by 1 Pith paper

  1. [1]

    Proof verification and the hardness of approximation problems

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM) , 45(3):501--555, 1998

    work page 1998

  2. [2]

    Probabilistic checking of proofs: A new characterization of NP

    Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP . Journal of the ACM (JACM) , 45(1):70--122, 1998

    work page 1998

  3. [3]

    Eli Ben - Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCP s of proximity, shorter PCP s, and applications to coding. SIAM J. Comput. , 36(4):889--974, 2006

    work page 2006

  4. [4]

    The complexity of rerouting shortest paths

    Paul Bonsma. The complexity of rerouting shortest paths. Theoretical computer science , 510:1--12, 2013

    work page 2013

  5. [5]

    Finding paths between 3-colorings

    Luis Cereceda, Jan Van Den Heuvel, and Matthew Johnson. Finding paths between 3-colorings. Journal of graph theory , 67(1):69--82, 2011

    work page 2011

  6. [6]

    Assignment testers: Towards a combinatorial proof of the PCP theorem

    Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM Journal on Computing , 36(4):975--1024, 2006

    work page 2006

  7. [7]

    The connectivity of B oolean satisfiability: computational and structural dichotomies

    Parikshit Gopalan, Phokion G Kolaitis, Elitza Maneva, and Christos H Papadimitriou. The connectivity of B oolean satisfiability: computational and structural dichotomies. SIAM Journal on Computing , 38(6):2330--2355, 2009

    work page 2009

  8. [8]

    Almost optimal time lower bound for approximating parameterized clique, CSP , and more, under ETH

    Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. Almost optimal time lower bound for approximating parameterized clique, CSP , and more, under ETH . arXiv preprint arXiv:2404.08870 , 2024

    arXiv 2024

Show all 22 references
  1. [9]

    Parameterized inapproximability hypothesis under exponential time hypothesis

    Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. Parameterized inapproximability hypothesis under exponential time hypothesis. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 24–35, New York, NY, USA, 2024. Associ...

    2024

  2. [10]

    Robust PCP s of Proximity and Shorter PCP s

    Prahladh Harsha. Robust PCP s of Proximity and Shorter PCP s . PhD thesis, Massachusetts Institute of Technology, 2004. Ph.D. thesis

    2004

  3. [11]

    Probabilistically checkable reconfiguration proofs and inapproximability of reconfiguration problems

    Shuichi Hirahara and Naoto Ohsaka. Probabilistically checkable reconfiguration proofs and inapproximability of reconfiguration problems. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, V...

    2024

  4. [12]

    Approximability of the subset sum reconfiguration problem

    Takehiro Ito and Erik D Demaine. Approximability of the subset sum reconfiguration problem. Journal of Combinatorial Optimization , 28:639--654, 2014

    2014

  5. [13]

    On the complexity of reconfiguration problems

    Takehiro Ito, Erik D Demaine, Nicholas JA Harvey, Christos H Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science , 412(12-14):1054--1065, 2011

    2011

  6. [14]

    Karthik C. S. and Pasin Manurangsi. On inapproximability of reconfiguration problems: PSPACE -hardness and some tight NP -hardness results. Electron. Colloquium Comput. Complex. , pages TR24--007, 2024

    2024

  7. [15]

    Improved hardness of approximating k-clique under ETH

    Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. Improved hardness of approximating k-clique under ETH . In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 285--306. IEEE , 2023

    2023

  8. [16]

    Two-query PCP with subconstant error

    Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. Journal of the ACM , 57(5):1--29, 2008

    2008

  9. [17]

    Introduction to reconfiguration

    Naomi Nishimura. Introduction to reconfiguration. Algorithms , 11(4):52, 2018

    2018

  10. [18]

    Gap preserving reductions between reconfiguration problems

    Naoto Ohsaka. Gap preserving reductions between reconfiguration problems. In 40th International Symposium on Theoretical Aspects of Computer Science , 2023

    2023

  11. [19]

    Alphabet reduction for reconfiguration problems

    Naoto Ohsaka. Alphabet reduction for reconfiguration problems. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia , volume 297 of LIPI...

    2024

  12. [20]

    Gap amplification for reconfiguration problems

    Naoto Ohsaka. Gap amplification for reconfiguration problems. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 1345--1366. SIAM , 2024

    2024

  13. [21]

    Reconfiguration problems on submodular functions

    Naoto Ohsaka and Tatsuya Matsuoka. Reconfiguration problems on submodular functions. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining , pages 764--774, 2022

    2022

  14. [22]

    The complexity of change

    Jan van den Heuvel. The complexity of change. Surveys in combinatorics , 409(2013):127--160, 2013

    2013

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.