Computer Science/Discrete Mathematics Seminar II

The sign-rank of a real matrix M is the smallest rank of any real matrix whose entries have the same sign as the entries of M . We exhibit a 2^n x 2^n matrix 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). 3. The first exponential lower bound on the size of threshold-of-majority circuits computing a function in AC^0 . Joint work with Alexander Sherstov (University of Texas).