Group:Complexity Group
Title: Pattern Matrix Method (Part 2 of 2)
Speaker: Chengu Wang Tsinghua university
Time: 2010-04-28 15:30-2010-04-28 17:00
Venue: FIT 1-222

Abstract:

This is the second part of pattern matrix method. First, I will recap the sketch of the proof of the main theorem, the approximation degree gives a lower bound of the quantum communication complexity, talked by Bangsheng last week. Then I will present the lower bound of the sign-rank of AC0, which is an application of the pattern matrix method.

The sign-rank of a matrix A=[A_{i,j}] with \plusminus 1 entries is the least rank of a real matrix B=[B_{i,j}] with A_{i,j}B_{i,j}>0 for all i,j. Let f(x,y)=AND_{i=1}^m OR_{j=1}^{m^2} (x_{i,j} AND y{i,j}), which is a function in AC0. A. Razborov and A. Sherstov show that the matrix [f(x,y)]_{x,y} has sign-rank exp(\Omega(m)) in FOCS 2008. This is the first exponential lower bound on the sign-rank of a function in AC0.

References:

1. The Pattern Matrix Method, Alexander A. Sherstov

2. The Sign-Rank of AC0, Alexander A. Razborov, Alexander A. Sherstov.




Short Bio: