{"id":"a926225d-46a0-4ed2-a3d7-fe1945d1665b","arxiv_id":"2507.01192","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Using a parallelization trick, the authors show that q-query PCPPs with soundness 1-epsilon directly imply PSPACE-hardness of (q+1)-CSP reconfiguration with soundness gap 1-epsilon, removing the prior factor-4 loss.","lead":"The paper proves a tighter conditional connection between probabilistic proof checking (PCPP) and the PSPACE-hardness of reconfiguration problems, improving the soundness gap from 1-epsilon/4 to 1-epsilon at the cost of one extra CSP arity. A smart generalist might read it because it sharpens the target for building better PCPPs, a central open problem in complexity theory.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main theorem depends on Theorem 12, asserted as 'Implicit in [KM24]' with no proof in this paper; if KM24's proof does not actually yield the stated PSPACE-hardness of 4-Parallel q-PCPP Reconfiguration, Theorem 2 collapses.","rationale":"The reader's verdict identifies the same weakest assumption, and I agree. The load-bearing nature of Theorem 12 is clear from the proof structure: Theorem 8/Corollary 10 is a static reduction that is well explained and appears correct as a reduction of promise problems, but a reduction from an unproved hard problem proves nothing. The paper is open about the gap by writing 'Implicit in [KM24]' and not proving the statement, so this is not an invented concern; it is an explicitly acknowledged dependency. Given that there is no machine-checked formalization and the proof is a sketch, the appropriate disposition remains conditional acceptance pending verification of Theorem 12's provenance. One secondary point worth noting is that the path-lifting step in Corollary 10 (assigning the v-coordinate along a reconfiguration path) is only sketched in Section 3.1; I did not make this the primary concern because the static soundness and completeness of Theorem 8 are clear and the path-lifting may be recoverable in the specific KM24 construction. The single decisive check is whether Theorem 12 actually exists in KM24 or can be proved from its methods.","tokens_in":8445,"tokens_out":31723,"duration_ms":330461,"concrete_test":"Obtain Karthik-Manurangsi (ECCC TR24-007) and examine the proof of the PSPACE-hardness of Gap_{1,1−ε/4} (q+1)-CSP Reconfiguration. Verify whether the proof contains, or immediately yields, the exact statement of Theorem 12: PSPACE-hardness of Gap_{1,1−ε} 4-Parallel q-PCPP Reconfiguration, with soundness threshold 1−ε and with reconfiguration steps changing one t-bit column. In particular, check the soundness extraction step (majority of the three unchecked rows) under column moves. If the exact statement or a direct derivation is absent, request that the authors provide a self-contained proof of Theorem 12; until then the main theorem should not be considered established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 2 is exactly the conjunction of Theorem 12 and Corollary 10. Theorem 12 (Section 3.2) is the only source of hardness for the base problem, yet it is not proved; the paper labels it 'Implicit in [KM24]' and gives no lemma-level derivation. This is a load-bearing omission: Corollary 10 only transfers hardness from Theorem 12 to CSP reconfiguration, so if Theorem 12 fails or has different parameters, the main theorem is unsupported. The paper's own review of KM24 (Section 3.1) derives only the weaker PSPACE-hardness of Gap_{1,1−ε/4} (q+1)-CSP Reconfiguration, with the factor 1/4 arising from letting three of four verifiers pass for free. The stated Theorem 12 requires the stronger and structurally different statement that Gap_{1,1−ε} 4-Parallel q-PCPP Reconfiguration is PSPACE-hard, where a reconfiguration step changes one column of t parallel bits and the YES condition is 'there exists i' at each step. Showing that KM24's soundness analysis survives this reformulation is a nontrivial argument and is not supplied. Until Theorem 12 is either located verbatim in KM24 with its proof, or proved here, the central implication is conditional on an unverified claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8737,"tokens_out":10754,"duration_ms":151505,"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":[{"comment":"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.","section":"Section 3.2, Theorem 12"},{"comment":"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.","section":"Theorem 8, completeness"},{"comment":"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).","section":"Corollary 10"}],"minor_comments":[{"comment":"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.","section":"Definition 4 and Definition 7"},{"comment":"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.","section":"Definition 9"},{"comment":"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.","section":"Section 3.2, paragraph after Theorem 8"},{"comment":"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.","section":"Corollary 3"}],"recommendation":"major_revision","confidential_remarks":"The central issue is whether Theorem 12 actually follows from KM24. The paper's own overview of KM24 derives a weaker 1−ε/4 statement, and the t-Parallel formulation with column-wise moves and existential witnesses is not visibly present in the cited work. The authors should be required to either reproduce a verbatim theorem from KM24 with proof or prove it in this paper. In addition, Corollary 10's handling of the extra variable v needs a real argument, not just \"applying our construction\". If these points are addressed, the paper would be a solid contribution; as it stands, the main theorem is only as reliable as an unverified attribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the new thing: Theorem 8's parallelization reduction is clean and correct. Stacking t PCPP verifiers that share the same query set per random seed, then encoding the choice of verifier into a single extra variable, gives a polynomial reduction from t-parallel PCPP reconfiguration to (q+1)-CSP reconfiguration with the same soundness parameter. That is a genuinely useful observation, and it removes the factor-4 loss in the KM24 construction. The paper also earns credit for formally defining parallelizable PCPPs and for being upfront that no new PCPP constructions are provided.\n\nThe problem is Theorem 12. The paper states it as \"Implicit in [KM24]\" and provides no proof. This is not a minor omission: Theorem 2 is exactly Corollary 10 plus Theorem 12. Without a lemma-level derivation of that hardness statement, the main theorem is unsupported. Worse, the paper's own overview of KM24 (Section 3.1) recovers only a gap of 1-epsilon/4 in the non-parallel construction, with the factor 1/4 earned by letting three of four verifiers pass for free. The leap from that to PSPACE-hardness of Gap_{1,1-epsilon} 4-Parallel q-PCPP Reconfiguration is a structural change in the problem: the YES condition becomes \"there exists i at each step,\" the NO condition is \"for all i,\" and reconfiguration steps change one column of parallel bits. It is not obvious that KM24's soundness analysis survives that reformulation. The authors may be right that it does, but they need to show it.\n\nSmaller issues: the definition of Gap t-Parallel q-PCPP Reconfiguration uses a disjunctive YES condition, which is fine for their reduction but needs careful handling in the soundness proof; the paper's use of Ohs24b's Lemma 5.4 in Corollary 3 is a citation to a published result, so that is acceptable.\n\nWho this is for: people working on RIH/PCPP tradeoffs. The parallelization framework is the main reusable asset.\n\nRecommendation: send it to a serious referee, but make clear the referee should ask for a proof of Theorem 12 or a precise pointer to KM24. If the authors can supply that, the paper becomes a solid contribution. As it stands, it is a promising abstract with a load-bearing gap.","headline":"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.","tokens_in":9267,"tokens_out":3757,"would_cite":true,"duration_ms":43680,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Any q-query PCPP with soundness 1−ε gives PSPACE-hardness for (q+1)-ary CSP reconfiguration.","keywords":["reconfiguration","CSP","PCPP","PSPACE-hardness","soundness gap","query complexity","parallelization","inapproximability"],"falsifier":"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.","tokens_in":8259,"feed_emoji":"🧩","tokens_out":6378,"duration_ms":72436,"temperature":0.7,"pith_summary":"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.","feed_headline":"Parallel PCPPs tighten reconfiguration hardness to one extra query","feed_subtitle":"A new reduction matches CSP reconfiguration's soundness to any PCPP's soundness, dropping the previous quarter loss.","key_machinery":"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 κ).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the base PCPP-to-reconfiguration reduction and the 4-parallel PCPP hardness stated as Theorem 12, which the paper parallelizes.","marker":"[KM24]"},{"why":"Provides Lemma 5.4 trading CSP arity for soundness, used to derive Corollary 3.","marker":"[Ohs24b]"},{"why":"Establishes PSPACE-completeness of exact Boolean satisfiability reconfiguration, the base hardness the constructions build on.","marker":"[GKMP09]"},{"why":"Formulates the Reconfiguration Inapproximability Hypothesis and gives gap-preserving reductions linking soundness gaps to reconfiguration.","marker":"[Ohs23]"},{"why":"Formalizes PCPPs as robust PCPs of proximity, whose parameters define the hypothesis in Theorem 2.","marker":"[BGH+06]"},{"why":"One of the parameterized-inapproximability works whose parallelization idea the paper adapts.","marker":"[LRSW23]"}],"fun_headline_variants":["Reconfiguration hardness now matches PCPP soundness exactly","Parallel PCPP check removes quarter loss in reconfiguration","Tighter PCPP-to-reconfiguration trade-off: one query, full gap","Exact soundness inheritance in CSP reconfiguration hardness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Reconfiguration hardness now matches PCPP soundness exactly","Parallel PCPP check removes quarter loss in reconfiguration","Tighter PCPP-to-reconfiguration trade-off: one query, full gap","Exact soundness inheritance in CSP reconfiguration hardness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000512,"raw_usage":{"total_tokens":2437,"prompt_tokens":842,"completion_tokens":1595,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":458,"completion_tokens_details":{"reasoning_tokens":1524}},"tokens_in":458,"tokens_out":1595,"duration_ms":15425,"temperature":1.0,"reasoning_tokens":1524,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:57:26.345334+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}