Group:Student Seminar
Title: Communication Complexity Lower Bound of Inner Product Modular m
Speaker: Chengu Wang University
Time: 2010-10-14 16:00-2010-10-14 17:00
Venue: FIT 1-222


Inner Product is a famous communication complexity problem that Alice holds x \in {0,1}^n and Bob holds y \in {0,1}^n, and they want to compute IP(x,y)=\sum_i x_i y_i \mod 2. It was well known that the deterministic, randomized and quantum communication complexity are all Theta(n). We generalize the IP problem to IP_m, which is to compute IP_m(x,y)=\sum_i x_i y_i \mod m. It was known that the deterministic communication complexity of IP_m is Theta(n log m) if m is a prime. We prove a tight quantum communication complexity of IP_m regardless of whether m is a prime or not.

In this talk, I will go through the proofs of some problems. Please feel free to join in and don't be intimidated by Joshua's complexity seminar.

Short Bio: