Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Dimension-free Relations in Communication Complexity
event speaker icon
Lianna Hambardzumyan (The Hebrew University of Jerusalem)
event date icon
Wednesday, 16.11.2022, 12:30
event location icon
Taub 201
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.