PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization

How hard is it to find a local optimum? If we are given a graph and want to find a locally maximal cut--meaning that the number of edges in the cut cannot be improved by moving a single vertex from one side to the other--then just iterating improving steps finds a local maximum since the size of the cut can increase at most $|E|$ times. If, on the other hand, the edges are weighted, this problem becomes hard for the class PLS (Polynomial Local Search). We are interested in optimization problems with {\em lexicographic costs}. For Max-Cut this would mean that the edges $e_1,\dots, e_m$ have costs $c(e_i) = 2^{m-i}$. For such a cost function, it is easy to see that finding a {\em global} Max-Cut is easy. In contrast, we show that it is PLS-complete to find an assignment for a 4-CNF formula that is locally maximal (when the clauses have lexicographic weights); and also for a 3-CNF when we relax the notion of ``local'' by allowing to switch two variables at a time. We use these results to answer a question in Scheder and Tantow, who showed that finding a lexicographic local minimum of a string $s \in \{0,1\}^n$ under the action of a list of given permutations $π_1, \dots, π_k \in S_{n}$ is PLS-complete. They ask whether the problem stays PLS-complete when the $π_1,\dots,π_k$ commute, i.e., generate an Abelian subgroup $G$ of $S_n$. In this work, we show that it does, and in fact stays PLS-complete even (1) when every element in $G$ has order two and also (2) when $G$ is cyclic, i.e., all $π_1,\dots,π_k$ are powers of a single permutation $π$. Additionally, we use it to reprove the hardness of computing an $α$ approximate Nash equilibria in congestion games by Skopalik and Vöcking and extend the result from step functions to exponential functions.