2025/07/01 by Venkatesan Guruswami, Guruswami, Venkatesan, Xuandi Ren +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2507.01192
openalex publication_date 2025/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.