Group:Complexity Group
Title: The Communication Lower Bound for Boolean Hidden Matching Problem
Speaker: Wei Yu Tsinghua university
Time: 2010-04-22 16:00-2010-04-22 17:00
Venue: FIT1-222


In this talk I will show the proof of lowerbound for the Boolean Hidden Matching problem. The Boolean Hidden Matching problem is a communication complexity problem where Alice gets a boolean vector x \in {0, 1}^n, Bob gets a perfect matching M on n vertices and a boolean vector w of length n/2. Let Mx denote the length n/2 boolean vector $(x_{M_{1,1}}\oplus x_{M_{1,2}}, ..., x_{M_{n/2,1}}\oplus x_{M_{n/2,2}}). It is promised that either Mx\oplus w = 1^{n/2} or Mx\oplus w = 0^{n/2}. The question is to distinguish these two cases.

We are going to show an Omega (sqrt (n)) lowerbound for this problem. The proof is based on basic concepts of Fourier analysis, and the so-called Bonami-Gross-Beckner, or Hypercontractivity inequality. This is also an interesting example to get communication complexity lowerbound from Fourier analysis since Ran Raz introduced the concept in 1995.

Short Bio: