STOC Conference 2022 Conference Paper
Approximate polymorphisms
- Gilad Chase
- Yuval Filmus
- Dor Minzer
- Elchanan Mossel
- Nitin Saurabh
For a function g ∶{0,1} m →{0,1}, a function f ∶ {0,1} n →{0,1} is called a g -polymorphism if their actions commute: f ( g ( row 1 ( Z )),…, g ( row n ( Z ))) = g ( f ( col 1 ( Z )),…, f ( col m ( Z ))) for all Z ∈{0,1} n × m . The function f is called an approximate g -polymorphism if this equality holds with probability close to 1, when Z is sampled uniformly. A pair of functions f 0 , f 1 ∶ {0,1} n → {0,1} are called a skew g -polymorphism if f 0 ( g ( row 1 ( Z )),…, g ( row n ( Z ))) = g ( f 1 ( col 1 ( Z )),…, f 1 ( col m ( Z ))) for all Z ∈{0,1} n × m .