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 >>>

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

We study the complexity of computing Boolean functions on general
Boolean domains by polynomial threshold functions (PTFs). A typical
example of a general Boolean domain is $\{1,2\}^n$. We are mainly
interested in the length (the number of monomials) of PTFs, with
their degree and weight being of secondary interest. We ... more >>>