Alexander A. Sherstov

Representations of Boolean functions by real polynomials

play an important role in complexity theory. Typically,

one is interested in the least degree of a polynomial

p(x_1,...,x_n) that approximates or sign-represents

a given Boolean function f(x_1,...,x_n). This article

surveys a new and growing body of work in communication

complexity that centers ...
more >>>

Alexander A. Sherstov

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial

that approximates $f$ within $1/3$ at every point. We prove that the function $\bigwedge_{i=1}^{n}\bigvee_{j=1}^{n}x_{ij}$,

known as the AND-OR tree, has approximate degree $\Omega(n).$ This lower bound is tight

and closes a ...
more >>>