Fourier Analysis in Boolean Promise Constraint Satisfaction

Speaker(s)

Katzper Michno

Affiliation

University of Warsaw

Language of the talk

English

Date

Feb. 4, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Fourier Analysis in Boolean Promise Constraint Satisfaction

Seminar

Seminar Automata Theory

---

Promise Constraint Satisfaction Problems (PCSPs) are NP problems defined by a pair of relational structures A and B over the same signature, where A admits a homomorphism to B. Given an input structure X, the task is to find a homomorphism from X to B, under the promise that X maps homomorphically to A.

A canonical example is the infamous Approximate Graph Coloring. For fixed integers k ≤ l, the problem asks for a proper l-coloring of a graph that is promised to be k-colorable. This problem is solvable in polynomial time for k ≤ 2 and is conjectured to be NP-hard for all other values, although hardness is unproven even for k = 3 and l = 6.

In this talk, we focus on Boolean PCSPs, where the underlying structures have domain {0,1}. The complexity classification of Boolean PCSPs also remains wide open. The most general result so far is a conditional dichotomy for the so-called Ordered PCSPs due to Brakensiek, Guruswami, and Sandeep, who show that every such PCSP is in P or is NP-hard, assuming the Rich 2-to-1 Conjecture (with perfect completeness) proposed by Braverman, Khot and Minzer. Although indirectly, the work of Brakensiek et al. introduced analytic techniques into the study of Boolean PCSPs. We extend these methods to more general settings, obtaining new tractability and hardness results for what we call Unate and Polynomial Threshold PCSPs.

We highlight the role of coordinate influence, a central concept in the Fourier analysis of Boolean functions, in the study of multivariate homomorphisms between the underlying structures of a PCSP. We explain how the phenomenon of sharp thresholds, originally studied for Erdős–Rényi graph properties, connects to PCSP complexity, and discuss state-of-the-art sources of hardness for Boolean PCSPs.

This is joint work with Demian Banakh and Marcin Kozik.

 

---