Haifa University - Dept. of CS Theory Seminar

Speaker : Adi Shraibman, Weizmann.

Title: "Lower bounds on randomized and quantum communication complexity based on factorization norms"

Date: Thursday, Dec. 6.

Place: Haifa U. Education Building, room 570.

Time: 12:15 - 13:30

Abstract:

We will describe a general framework for proving lower bounds on randomized and quantum communication complexity
that generalizes most of the known lower bounds. In particular we show that almost all of the known lower bounds
can be explained using duality theory.

Joint work with Nati Linial.