PMMSNP problems forbidding monochromatic cliques admit a full complexity dichotomy under the Rich 2-to-1 Conjecture.
35 Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.CC 2years
2026 2roles
background 1polarities
background 1representative citing papers
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
-
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.