讨论组:学生讲座
标题:Communication Complexity of Matrix Rank in F_2
演讲人: 王晨谷 University
时间: 2011-03-10 16:30-2011-03-10 17:30
地点:FIT 1-222

内容:

Consider the following communication game. Alice holds a n by n boolean matrix x, and Bob holds a n by n boolean matrix y. Their goal is to compute the rank of x+y in the finite field F_2. In this definition, the function they want to compute is a multi-value function. However, we usually prefer functions which returns only 0 or 1. Chu and Schnitger proved that Alice and Bob need to transfer Omega(n^2) bits to determine whether x+y is full rank in F_2 if the protocol is deterministic. We almost proved that Alice and Bob need to transfer Omega(n^2) bits to determine the parity of the rank of x+y in F_2 even if they use quantum protocols. In this talk, I will show our proof of the Omega(n^2) result for quantum protocols, and propose some open questions.