Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $\phi$ where each clause contains exactly $k$ literals, along with a pair of its satisfying assignments. The objective is transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing the minimum fraction of satisfied clauses of $\phi$ throughout the transformation. In this paper, we demonstrate that the optimal approximation factor for Maxmin E$k$-SAT Reconfiguration is $1-\mathrm{\Theta }\left(\frac{1}{k}\right)$. On the algorithmic side, we develop a deterministic $(1-\frac{1}{k-1}-\frac{1}{k})$-factor approximation algorithm for every $k\ge 3$. On the hardness side, we show that it is $\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}$-hard to approximate this problem within a factor of $1-\frac{1}{10k}$ for every sufficiently large $k$. Note that an $\mathsf{NP}$ analogue'' of Maxmin E$k$-SAT Reconfiguration is Max E$k$-SAT, whose approximation threshold is $1-\frac{1}{2^k}$ shown by Håstad (JACM 2001). To the best of our knowledge, this is the first reconfiguration problem whose approximation threshold is (asymptotically) worse than that of its $\mathsf{NP}$ analogue. To prove the hardness result, we introduce a new non-monotone’’ test, which is specially tailored to reconfiguration problems, despite not being helpful in the PCP regime.