Previous Conferences & Workshops

Oct
01
2007

Computer Science/Discrete Mathematics Seminar I

The Pattern Matrix Method for Lower Bounds on Quantum Communication
Alexander Sherstov
11:15am|S-101

In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior...