文章基本信息

标题：Dimension-free Bounds and Structural Results in Communication Complexity
本地全文：下载
作者：Lianna Hambardzumyan ; Hamed Hatami ; Pooya Hatami 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to perhaps the more common framework in communication complexity where poly-logarithmic dependencies on the number of input bits are tolerated. Dimension-free bounds are also closely related to structural results, where one seeks to describe the structure of Boolean matrices and functions that have low complexity. We prove such theorems for several communication and query complexity measures as well as various matrix and operator norms. In several other cases we show that such bounds do not exist. We propose several conjectures, and establish that, in addition to applications in complexity theory, these problems are central to characterization of the idempotents of the algebra of Schur multipliers, and could lead to new extensions of Cohen's celebrated idempotent theorem regarding the Fourier algebra.
关键词：Communication complexity;lifting theorems;matrix norms;query complexity