Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PROBABILISTICALLY CHECKABLE PROOFS:
Reports tagged with probabilistically checkable proofs:
TR26-136 | 30th July 2026
Shuichi Hirahara, Naoto Ohsaka

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

In the Maxmin $q$-CSP Reconfiguration problem, given a satisfiable $q$-CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the other by repeatedly changing the value assigned to a single variable. The objective is to find such a transformation that maximizes the minimum ... more >>>




ISSN 1433-8092 | Imprint