1 citations · 1 across the 4 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Towards infinite PCSP: a dichotomy for monochromatic cliques
Demian Banakh, Alexey Barsukov, Tamio-Vesa Nakajima
The logic MMSNP is a well-studied fragment of Existential Second-Order logic that, from a computational perspective, captures finite-domain Constraint Satisfaction Problems (CSPs)…
cs.CC2026
Boolean PCSPs through the lens of Fourier Analysis
Demian Banakh, Katzper Michno
We develop an analytical framework for Boolean promise constraint satisfaction problems (PCSPs) that studies polymorphisms through the notion of influence from Fourier analysis of…
cs.CC2024★ 1 cited
Injective hardness condition for PCSPs
Demian Banakh, Marcin Kozik
We present a template for the Promise Constraint Satisfaction Problem (PCSP) which is NP-hard but does not satisfy the current state-of-the-art hardness condition [ACMTCT'21]. We i…