Establishes PLS-completeness for lexicographic local search in 4-CNF and 3-CNF (double flips), and for Abelian permutation orbit minimization even when groups are cyclic or consist of involutions, with applications to bounded congestion games.
On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence
3 Pith papers cite this work, alongside 797 external citations. Polarity classification is still indexing.
3
Pith papers citing it
797
external citations · OpenAlex
verdicts
UNVERDICTED 3representative citing papers
A general technique establishes equivalence of deterministic and randomized black-box reductions from complete problems in PPP, PPAD, PPA, and t-PPP to TFNP problems, strengthening known separations to randomized versions.
Assuming a factorization hypothesis on P-time definable linear orders, the paper outlines a nonstandard model of bounded arithmetic satisfying P-minimization but violating the P-tournament principle.
citing papers explorer
-
PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
Establishes PLS-completeness for lexicographic local search in 4-CNF and 3-CNF (double flips), and for Abelian permutation orbit minimization even when groups are cyclic or consist of involutions, with applications to bounded congestion games.
-
Randomized separations in black-box TFNP
A general technique establishes equivalence of deterministic and randomized black-box reductions from complete problems in PPP, PPAD, PPA, and t-PPP to TFNP problems, strengthening known separations to randomized versions.
-
Minimization Principle for Polynomial-Time Predicates and Forcing in Bounded Arithmetic
Assuming a factorization hypothesis on P-time definable linear orders, the paper outlines a nonstandard model of bounded arithmetic satisfying P-minimization but violating the P-tournament principle.