A Boolean function f on n variables is called a polymorphism of another Boolean function g on m variables if their operations commute. That is, for all {0,1}-matrix Z of dimension (n x m), f(g(row1(Z)), g(row2(Z)), ..., g(rown(Z))) = g(f(col1(Z)), f(col2(Z)), ...,f(colm(Z))). The function f is called an approximate polymorphism if this equality holds with probability close to 1 when Z is sampled uniformly.
The problem of characterizing the structure of exact or approximate polymorphisms appears in several different contexts, namely in understanding the complexity of CSPs, property testing, and social choice theory.
In this talk, we will give a characterization of exact polymorphisms, and also show that approximate polymorphisms must be close to exact polymorphisms. Our results generalize the classical linearity testing result of Blum et al. as well as the recent AND testing result of Filmus et al.
This is based on a joint work with Gilad Chase, Yuval Filmus and Dor Minzer.
Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
