PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
By: Venkatesan Guruswami, Xuandi Ren, Kewen Wu
Potential Business Impact:
Makes hard computer puzzles easier to solve.
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.
Similar Papers
Towards an algebraic approach to the reconfiguration CSP
Data Structures and Algorithms
Lets computers change solutions step-by-step.
Gap-preserving reductions and RE-completeness of independent set games
Quantum Physics
Makes finding hidden patterns in games impossible.
Derandomised tensor product gap amplification for quantum Hamiltonians
Quantum Physics
Makes hard computer problems easier to solve.