The approximate degree of a Boolean function f{0,1}^n→{0,1} is
the minim...
We prove that for every decision tree, the absolute values of the Fourie...
The classical communication complexity of testing closeness of discrete
...
The ϵ-approximate degree of a function f X →{0, 1} is
the least degree o...
We study the approximation of halfspaces h:{0,1}^n→{0,1} in the
infinity...
The threshold degree of a Boolean function f{0,1}^n→{0,1} is
the minimum...
The approximate degree of a Boolean function f(x_1,x_2,...,x_n) is
the m...
A basic goal in complexity theory is to understand the communication
com...