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


The pattern matrix method is a technique for proving communication lower bounds, designed by Alexander Sherstov. The main object that is considered is *pattern matrix*.

Consider the following communication, Alice has a string x of {0,1}^n, and Bob has a t-sized set V of {1,2,...n}, and they wish to compute f(x|V), where f is a {0,1}^t->{0,1} function. A particular instance of Bob's input would be from each of {1,2,...n/t}, {n/t+1,...2n/t}, ..., {(t-1)n/t+1, ... ,n}, pick one element. And if V is constrained on this kind of input, then the pattern matrix is defined as the 2^n by (n/t)^t matrix, each entry corresponds to the output of f under the input.

In this talk, I will talk about the basic definitions and facts about pattern matrices. I will sketch a theorem concerning the eigenvalues of a pattern matrix, which is crucial in the second part of this topic. In the next week, Chengu will present sign-rank of AC0, which is an application of the pattern matrix method.


1. The Pattern Matrix Method, Alexander A. Sherstov

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


Short Bio: