| Lower bounds in communication complexity based on factorization norms (2007) | |||||||||||||||
Abstract | |||||||||||||||
| We introduce a new method to derive lower bounds on randomized and quantum communication complexity. Our method is based on factorization norms, a notion from Banach Space theory. As we show, our bounds compare favorably with previously known bounds. Aside from the new results that we derive, our method yields new and more transparent proofs of some known results as well. Among our new results we extend some known lower bounds to the realm of quantum communication complexity with entanglement. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||