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 sign-rank 2^{Omega(m)}.
This in particular implies that Sigma_2^{cc}\not\subseteq UPP^{cc},
which solves a long-standing open problem posed by Babai, Frankl,
and Simon (1986).

Our result additionally implies a lower bound in learning theory.
Specifically, let phi_1,...,phi_r : {0,1}^n -> R be functions
such that every DNF formula f:{0,1}^n->{+1,-1} of polynomial size has
the representation f=sign(a_1*phi_1+...+a_r*phi_r) for
some reals a_1,...,a_r. We prove that then r> 2^{Omega(n^{1/3})},
which essentially matches an upper bound of 2^{tilde O(n^{1/3})}
due to Klivans and Servedio (2001).

Finally, our work yields the first exponential lower bound on the
size of threshold-of-majority circuits computing a function
in AC^0. This substantially generalizes and strengthens the
results of Krause and Pudlak (1997).