Showing cs.CCShow all
2 papers · 1 filter
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.CC2025
On Boolean PCSPs with Polynomial Threshold Polymorphisms
Katzper Michno
In pursuit of a deeper understanding of Boolean Promise Constraint Satisfaction Problems (PCSPs), we identify a class of problems with restricted structural complexity, which could…