Tel-Aviv University - Computer Science Colloquium

Sunday, June 11, 2006, 11:15-12:15

Room 309
Schreiber Building


Nati Linial

Hebrew University

Title: Some new perspectives on complexity and their applications




All the material I will present is included in Adi Shraibman's thesis.

We have developed a new point of view on complexity in general and have

specifically investigated various complexity measures of sign matrices. In

this talk I will introduce the general approach we are taking. If time permits, I

will indicate how this approach allows us to prove a new lower bound in quantum

communication complexity.