Speaker:  Alexander Razborov, Institute for Advanced Study 

 

                         The Sign-Rank of $AC0$

 

The sign-rank of a matrix $M$ with $\pm 1$ entries is the smallest rank of a real matrix
$A$ such that $M_{ij}=sign(A_{ij})$ for all $i,j$. We exhibit a $2^n\times 2^n$ matrix $M$
computable by depth 2 circuits of polynomial size whose sign-rank is exponential in $n$. 
Our result has the following immediate applications.

 

1. In the context of communication complexity alternations can be more powerful than 
unbounded-error probabilism. This solves a long-standing open problem asked in the seminal
paper by Babai, Frankl and Simon (1986).

 

2. Exponential lower bounds on the dimension complexity of the class of all DNF formulas.
Our bound almost matches the upper bound proved by Klivans and Servedio (2001) and provides
apparently the first unconditional exponential lower bound for PAC learning of DNF formulas
in a reasonable model.

 

3. The first exponential lower bound on the size of thershold-of-majority circuits 
computing a function in $AC0$.

 

Joint work with Alexander Sherstov (U. of Texas)