The threshold degree of a function $f\colon\{0,1\}^n\to\{-1,+1\}$ is the least degree of a real polynomial $p$ with $f(x)\equiv\mathrm{sgn}\; p(x).$ We prove that the intersection of two halfspaces on $\{0,1\}^n$ has threshold degree $\Omega(n),$ which matches the trivial upper bound and completely answers a question due to Klivans (2002). The best ... more >>>

The threshold degree of a Boolean function $f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We construct two halfspaces on $\{0,1\}^n$ whose intersection has threshold degree $\Theta(\sqrt n),$ an exponential improvement on previous lower bounds. This solves an open problem due to Klivans (2002) and ... more >>>

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

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0 for all i,j. We obtain the first exponential lower bound on the sign-rank of a function in AC^0. Namely, let f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}). We show that the matrix [f(x,y)]_{x,y} has ... more >>>

Let A_1,...,A_n be events in a probability space. The approximate inclusion-exclusion problem, due to Linial and Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve this problem optimally for each k. We study the following more general question: ... more >>>

The sign-rank of a real matrix M is the least rank of a matrix R in which every entry has the same sign as the corresponding entry of M. We determine the sign-rank of every matrix of the form M=[ D(|x AND y|) ]_{x,y}, where D:{0,1,...,n}->{-1,+1} is given and x ... more >>>

In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior entanglement. This was proved by the _multidimensional_ discrepancy method. We give an entirely different ... more >>>

We solve an open problem of Kushilevitz and Nisan (1997) in communication complexity. Let $R_{eps}(f)$ and $D^{mu}_{eps}(f)$ denote the randomized and $mu$-distributional communication complexities of f, respectively ($eps$ a small constant). Yao's well-known Minimax Principle states that R_{eps}(f) = max_{mu} { D^{mu}_{eps}(f) }. Kushilevitz and Nisan (1997) ask whether this ... more >>>

We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time ... more >>>