Approximate polymorphisms

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 .

Authors

• Gilad Chase
• Yuval Filmus
• Dor Minzer
• Elchanan Mossel
• Nitin Saurabh

Keywords

• polymorphisms
• property testing
• social choice theory