Sunday, June 11, 2006, 11:15-12:15
Room 309
--------------------------------------------------------------------------------
Nati Linial
Title: Some new perspectives on complexity and their
applications
Abstract:
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.