Gives an approximation algorithm for satisfiable instances of generalized linear equation CSPs over finite groups that is optimal for certain S, while the predicate remains approximation resistant on almost-satisfiable instances.
On Rich 2-to-1 Games , booktitle =
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.CC 3years
2026 3roles
background 1polarities
background 1representative citing papers
PMMSNP problems forbidding monochromatic cliques admit a full complexity dichotomy under the Rich 2-to-1 Conjecture.
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.
citing papers explorer
-
Optimal Inapproximability of Generalized Linear Equations over a Finite Group
Gives an approximation algorithm for satisfiable instances of generalized linear equation CSPs over finite groups that is optimal for certain S, while the predicate remains approximation resistant on almost-satisfiable instances.
-
Towards infinite PCSP: a dichotomy for monochromatic cliques
PMMSNP problems forbidding monochromatic cliques admit a full complexity dichotomy under the Rich 2-to-1 Conjecture.
-
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.