{"id":"14eca2b7-3f14-43dd-868c-ae11ddd01e90","arxiv_id":"2607.28099","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"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.","lead":"The paper proves that approximating Maxmin q-CSP Reconfiguration better than 1/2^{q-1} is PSPACE-hard for every q≥2, and that slightly worse approximations sit in NP when a perfect path exists. This pins down the exact hardness threshold for a core reconfiguration problem and separates P, NP, and PSPACE regimes by arity.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the two places where the argument could fail (PCRP seed regularity and the new tester). Both are argued in detail and sit inside the accepted toolkit of the area; the gap-amplifying reduction (Lem 6.2), unique-decoding claim (Cl 6.6), interpolation (Cl 6.7), and the NP-membership sparsification (Thm 7.1) all check out against the stated theorems. No hidden assumption on irregularity, alphabet growth, or expander parameters appears to break the 1/2^{q-1} threshold. ChatGPT assistance is confined to the algorithmic §§7–8 and is disclosed. Consequently the ACCEPT / high-confidence verdict stands; the concrete test above is only a sanity check on the most intricate new analytic piece, not a suspected flaw.","tokens_in":74421,"tokens_out":524,"duration_ms":24149,"concrete_test":"Independently re-derive the key soundness step of Thm 5.8 (the p^{1/(q-1)} agreement lower bound) from Prop 5.2 + Lem 5.13–5.16 without invoking the specific ε_{k,ℓ,m} schedule of (5.29); if the same 1/2^{q-1} exponent still emerges for the parameter regime ℓ=Θ(√k), m=Θ(√ℓ) used in §6, the tester analysis is robust.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central dichotomy (PSPACE-hardness of GAP_{1,1/2^{q-1}+ε} vs NP-membership of the complementary factor under perfect completeness) rests on two pillars the reader already flags: the PCRP seed for regular GAP_{1,s} 2-CSP Reconfiguration, and the soundness analysis of the new tolerant q-query direct-product tester (Thm 5.1/5.6 + expander hitting on the Johnson graph). Both are standard accepted prior art plus a careful but conventional extension of Dinur–Goldenberg / IKW-style arguments; the manuscript supplies complete proofs (including the long Appendix A uniqueness/decoding argument) with no internal contradiction visible on a careful read of the reduction architecture (unique decoding of adjacent F^{(t)}, near-path interpolation, low/high-degree sparsification, 2q-wise buckets). I do not find a further load-bearing gap that would overturn the claimed threshold.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies the approximability of Maxmin q-CSP Reconfiguration. It proves that for every q≥2 and ε>0, approximating the problem within a factor of 1/2^{q-1}+ε is PSPACE-hard (even on regular instances), via a gap-amplifying reduction from the PCRP theorem that uses a new tolerant q-query direct-product tester. Complementarily, it shows that a (1/2^{q-1}-ε)-factor approximation lies in NP in the perfect-completeness case (by low/high-degree sparsification and random-order interpolation), and gives a deterministic polynomial-time algorithm achieving the same factor on regular instances. Together these establish an optimal PSPACE-hardness threshold under NP\neq PSPACE, with a striking complexity dichotomy: for q=2 the threshold separates P from PSPACE-complete, while for q≥4 it separates NP-complete from PSPACE-complete.","tokens_in":74645,"tokens_out":814,"duration_ms":12433,"significance":"The result closes the open problem of Guruswami et al. on the optimal PSPACE threshold for Maxmin 2-CSP Reconfiguration and substantially strengthens prior PSPACE-hardness factors of Gur–Minzer–Weissenberg–Zheng. The discovery that approximate reconfiguration can be NP-complete (rather than only P or PSPACE-complete) is conceptually new and forces a finer complexity landscape for the area. The technical contribution—a tolerant multi-query direct-product tester whose soundness yields the precise 1/2^{q-1} exponent via expander hitting on the Johnson graph—is of independent interest and is supplied with a complete analysis (including the long uniqueness/decoding argument of Appendix A). The matching algorithmic upper bounds (NP membership and a deterministic regular-case algorithm) make the threshold tight under standard assumptions.","major_comments":[],"minor_comments":[{"comment":"In the proof overview (Section 2.1.1) the informal Claims 2.4–2.6 are stated with asymptotic notation that is later made precise only in Section 6; a forward pointer to the exact statements (Claims 6.6–6.8) would help the reader.","section":"Section 2.1.1"},{"comment":"Table 1 footnote † asserts that sequential repetition yields the 0.81-factor for q=4 from the q=2 result of GMWZ26; a one-sentence justification or citation of the precise repetition lemma used would remove any ambiguity.","section":"Table 1"},{"comment":"The parameter regime ℓ=Θ(√k), m=Θ(√ℓ) is used throughout Sections 5–6; stating once that these choices simultaneously make ε_{k,ℓ,m}=k^{-Ω(1)} and keep the completeness error o(1) would tighten the exposition.","section":"Section 5"},{"comment":"In Lemma 7.2 the concrete constant 100 appearing in the degree cutoff Δ=ε^{2}m/(100q log n) is never justified beyond “sufficiently large”; a short calculation showing where the 100 arises from McDiarmid would improve reproducibility.","section":"Lemma 7.2"},{"comment":"Several “O_q” and “Ω(1)” hide dependencies on the alphabet size σ that become relevant when σ grows with k (as it does after the reduction); making the dependence explicit in the final statements of Theorems 6.1 and 7.1 would be cleaner.","section":"Theorems 6.1, 7.1"}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the explicit open question from GKMRW25: the tight PSPACE threshold for MaxMin-2-CSP reconfiguration is exactly 1/2, and the same 1/2^{q-1} barrier holds for every arity. That is the headline. The matching NP-membership under perfect completeness (and a deterministic poly-time algorithm on regular instances) makes the dichotomy clean under NP ≠ PSPACE.\n\nWhat is actually new is the tolerant q-query direct-product tester (Thm 5.1) together with the gap-amplifying reduction that reaches the information-theoretic floor. Earlier PCPP-style arguments stopped at 2/3-type factors; the zig-zag Johnson-graph walk plus expander hitting gives the right exponent. The unique-decoding-plus-interpolation argument that turns adjacent proofs into a near-path is standard in outline but carefully executed, and the low/high-degree sparsification for the NP side is the right tool. Appendices A–B supply the long uniqueness analysis and the omitted reduction claims; the architecture has no internal contradiction I can see.\n\nSoft spots are real but proportionate. Hardness still seeds from the PCRP theorem on regular GAP_{1,s} 2-CSP; if that seed ever failed the whole tower collapses, but PCRP is published prior work. The tester soundness is a careful extension of Dinur–Goldenberg / IKW, not a black box, and the constants are not machine-checked—Appendix A is long. The open status of the exact 1/4-ε regime for q=3 is acknowledged honestly. ChatGPT use on the algorithmic sections is disclosed and does not touch the hardness core.\n\nThis is for people who work on reconfiguration complexity or product testing. A serious referee will want to check the expander-hitting constants and the unique-decoding claims, but the paper is already in shape for that. I would bring it to reading group, cite the threshold statements, and send it to peer review.","headline":"Closes the GKMRW open problem with a matching 1/2^{q-1} PSPACE threshold for every arity, via a new tolerant q-query product tester and clean gap amplification.","tokens_in":75327,"tokens_out":502,"would_cite":true,"duration_ms":12756,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","68W25"],"pacs":[],"model":"grok-4.5","headline":"Approximating Maxmin q-CSP reconfiguration is PSPACE-hard above 1/2^{q-1} and lies in NP just below it.","keywords":["Maxmin q-CSP Reconfiguration","PSPACE-hardness of approximation","direct product testing","reconfiguration","gap amplification","approximation threshold"],"falsifier":"Exhibit either a polynomial-time algorithm that beats factor 1/2^{q-1}+ε on regular q-CSP reconfiguration instances, or a proof that GAP_{1,1/2^{q-1}-ε} q-CSP reconfiguration is PSPACE-hard, for any fixed q≥2.","tokens_in":75254,"feed_emoji":"⚡","tokens_out":896,"duration_ms":15342,"temperature":0.7,"pith_summary":"The paper pins down the exact approximation threshold for Maxmin q-CSP Reconfiguration: given a satisfiable q-ary constraint system and two satisfying assignments, find a path that flips one variable at a time while keeping the worst intermediate assignment as good as possible. For every arity q at least 2, any factor strictly better than 1/2^{q-1} is PSPACE-hard, even on regular instances; any factor strictly worse is achievable by a short certificate and therefore lies in NP whenever a perfect path exists. The matching upper and lower bounds settle an open question for the q=2 case and reveal a surprising complexity split: for binary constraints the threshold separates P from PSPACE, while for arity four and higher it separates NP-completeness from PSPACE-completeness. A deterministic polynomial-time algorithm recovers the same factor on regular instances. The results show that reconfiguration approximability can sit in three distinct complexity regimes rather than the two that earlier work had assumed.","feed_headline":"q-CSP reconfiguration hard above 1/2^{q-1}, easy below","feed_subtitle":"Matching PSPACE-hardness and NP membership fix the exact approximation threshold for every arity","key_machinery":"A tolerant q-query direct-product tester on the Johnson graph. Its soundness converts acceptance probability p into approximate agreement with a genuine direct product at rate roughly p^{1/(q-1)}, which supplies the precise 1/2^{q-1} hardness factor when the tester is composed with a gap-amplifying reduction from 2-CSP reconfiguration.","core_discovery":"For every integer q≥2 and every ε>0, Maxmin q-CSP Reconfiguration is PSPACE-hard to approximate within factor 1/2^{q-1}+ε (even when every variable appears equally often), while a (1/2^{q-1}-ε)-factor approximation is in NP in the perfect-completeness case; the two statements together are optimal under NP≠PSPACE.","pith_inferences":["The open complexity of a (1/4-ε)-factor approximation for ternary CSPs is the natural next target; a poly-time algorithm would unify the q=2 and q=3 pictures, while NP-hardness would require highly irregular gadgets.","The same tolerant multi-query tester may yield tight thresholds for other reconfiguration problems whose natural encodings admit direct-product lifts.","The appearance of an NP-complete intermediate regime suggests that many PSPACE-complete reconfiguration problems may hide similar NP islands once approximation is allowed."],"forward_implications":["For binary CSPs the approximation threshold 1/2 cleanly separates polynomial time from PSPACE-completeness.","For arity-four and higher CSPs the same threshold separates NP-completeness from PSPACE-completeness—the first reconfiguration problem known to exhibit this three-way split.","A deterministic poly-time algorithm already achieves the optimal factor on every regular instance.","Any future improvement of the hardness factor would require a stronger seed than the existing PCRP theorem supplies."],"fun_headline_variants":["Maxmin q-CSP reconfig is PSPACE-hard past 1/2^{q-1}","Optimal PSPACE threshold for q-CSP reconfiguration approx","q-CSP reconfig: hard above 1/2^{q-1}, NP below","Exact approx threshold fixed for Maxmin q-CSP reconfig","PSPACE-hardness matches NP membership at 1/2^{q-1}"],"cache_read_input_tokens":65664,"weakest_assumption_plain":"The argument starts from a known constant-gap PSPACE-hard instance of 2-CSP reconfiguration on regular graphs; if that seed hardness fails, the optimal factor for larger arities does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Maxmin q-CSP reconfig is PSPACE-hard past 1/2^{q-1}","Optimal PSPACE threshold for q-CSP reconfiguration approx","q-CSP reconfig: hard above 1/2^{q-1}, NP below","Exact approx threshold fixed for Maxmin q-CSP reconfig","PSPACE-hardness matches NP membership at 1/2^{q-1}"]},"model":"grok-4.5","effort":"low","cost_usd":0.003788,"raw_usage":{"total_tokens":1177,"prompt_tokens":764,"num_sources_used":0,"completion_tokens":108,"cost_in_usd_ticks":37884000,"prompt_tokens_details":{"text_tokens":764,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":305,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":764,"tokens_out":108,"duration_ms":5772,"temperature":1.0,"reasoning_tokens":305,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T17:51:25.260249+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit either a polynomial-time algorithm that beats factor 1/2^{q-1}+ε on regular q-CSP reconfiguration instances, or a proof that GAP_{1,1/2^{q-1}-ε} q-CSP reconfiguration is PSPACE-hard, for any fixed q≥2.","supporting_citations":[],"review_version":1}