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
-
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.