The metaproblem for coset-generating polymorphisms is NP-complete, and promise metaproblems for Maltsev-plus-abelian-heap pairs are in P even when the individual metaproblems remain open.
Algebraic Approach to Promise Constraint Satisfaction
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 6roles
background 1polarities
background 1representative citing papers
Aggregation mechanisms for surjective classifications are nearly dictatorial with high probability unless functions are nearly constant, with a full characterization of always-surjective mechanisms.
Fourier analysis of Boolean functions yields two phenomena—preservation of coordinate influence under random 2-to-1 minors and sharp thresholds—that classify hardness and tractability for Boolean PCSP minions of unate or polynomial threshold functions, extending prior ordered-PCSP results.
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
The paper reformulates polymorphisms in CSPs and PCSPs as right Kan extensions and supplies purely categorical proofs that complexity is determined by these structures.
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
citing papers explorer
-
The complexity of finding coset-generating polymorphisms and the promise metaproblem
The metaproblem for coset-generating polymorphisms is NP-complete, and promise metaproblems for Maltsev-plus-abelian-heap pairs are in P even when the individual metaproblems remain open.
-
Classification aggregation: a quantitative impossibility theorem
Aggregation mechanisms for surjective classifications are nearly dictatorial with high probability unless functions are nearly constant, with a full characterization of always-surjective mechanisms.
-
Boolean PCSPs through the lens of Fourier Analysis
Fourier analysis of Boolean functions yields two phenomena—preservation of coordinate influence under random 2-to-1 minors and sharp thresholds—that classify hardness and tractability for Boolean PCSP minions of unate or polynomial threshold functions, extending prior ordered-PCSP results.
-
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
-
A categorical perspective on constraint satisfaction: The wonderland of adjunctions
The paper reformulates polymorphisms in CSPs and PCSPs as right Kan extensions and supplies purely categorical proofs that complexity is determined by these structures.
-
Hardness and Approximation for Coloring Digraphs
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.