Boolean PCSPs through the lens of Fourier Analysis
2026-04-24 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors created a math framework to better understand certain computer problems called Boolean Promise Constraint Satisfaction Problems (PCSPs) using ideas from Boolean function analysis. They built on earlier work and found two key behaviors in mathematical objects called minions that can signal whether these problems are easy or hard: how influence on inputs is preserved and sudden changes known as sharp thresholds. Their work applies these findings to wider types of functions than before, leading to new insights about when problems can be solved efficiently or not.
Boolean functionsPromise Constraint Satisfaction Problems (PCSPs)polymorphismsFourier analysiscoordinate influenceminionssharp thresholdsunate functionspolynomial threshold functions
Authors
Demian Banakh, Katzper Michno
Abstract
We develop an analytical framework for Boolean Promise Constraint Satisfaction Problems (PCSPs) that studies polymorphisms through the notion of influence from Fourier analysis of Boolean functions. Extending the work of Brakensiek, Guruswami, and Sandeep [ICALP'21] on Ordered PCSPs, we identify two general phenomena in Boolean minions indicative of hardness or tractability: (1) preservation of coordinate influence under random 2-to-1 minors and (2) the presence of sharp thresholds. We demonstrate that these phenomena occur in broader settings than previously established, yielding new hardness/tractability results for minions consisting of unate or polynomial threshold functions.