[Colloquium] Alexander Razborov - TTI-C Talk

[Gary Hamburg]

When:   Tuesday, November 27, 2007 @ 10:00 AM
 
Where:  TTI-C Conference Room
 
Who:    Alexander Razborov - Institute for Advanced Study, Princeton NJ.
 
Topic:  The Sign-Rank of $AC^0$
 
 
 
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 $AC^0$.
 
Joint work with Alexander Sherstov (U. of Texas)
 
 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20071126/8715ab8e/attachment.html