The Taub Faculty of Computer Science Events and Talks

In this talk we will discuss dimension-free relations between basic communication and query complexity measures and various matrix norms. Dimension-free relations are inequalities that bound a parameter as a function of another parameter without dependency on the number of input bits. This is in contrast to the more common framework in communication complexity where polylogarithmic dependencies are tolerated. Dimension-free bounds are closely related to structural results, where one seeks to describe the structure of Boolean matrices and functions that have “low complexity”. We prove such bounds for several communication and query complexity measures as well as various matrix and operator norms. We also propose several conjectures, and establish connections to graph theory, operator theory, and harmonic analysis. The talk is based on joint work with Hamed Hatami and Pooya Hatami.