The Setting
Two points of the -dimensional Boolean cube are neighbours when they differ in exactly one coordinate, and a function on the cube either changes its value across such an edge or keeps it. Its average sensitivity measures how often it changes, direction by direction. For a polynomial threshold function of degree , the sign of a real multilinear polynomial of degree at most evaluated at the points of the cube, the Gotsman-Linial conjecture concerns how large the average sensitivity can be in terms of and .
The Definition
Definition 1. The Boolean cube is the set of strings of Boolean values, true or false, each read as a sign: (1)✦ For , the -th coordinate of a point is the real number (2)✦ For and a coordinate , the point is with its -th coordinate reversed: (3)✦ The sign of a real number is the number (4)✦ For a function and a coordinate , the sensitive vertices of in direction form the set of the points at which reversing the -th coordinate changes the value of : (5)✦ With a uniform random point of , the average sensitivity of a function is the number (6)✦ A real polynomial in the variables , with real coefficients and exponent vectors of nonnegative integers, is multilinear when no variable occurs in a monomial of with an exponent above one: (7)✦ The value of a real polynomial in at a point is evaluated at the coordinates (2) of : (8)✦ The polynomial threshold function of a real polynomial in is the function given by (9)✦
What Is Checked
The definitions are stated over the cube of strings of Boolean values, over real-valued functions on , and over polynomials in with real coefficients.