A Hierarchy for Constant Communication Complexity
Andris Ambainis, Hartmut Klauck, Debbie Lim · 2025
Read A Hierarchy for Constant Communication Complexity by Andris Ambainis, Hartmut Klauck, Debbie Lim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22004.txt.
Introduction
Andris Ambainis, Hartmut Klauck, and Debbie Lim classify the measures of communication complexity in this 2025 theoretical computer science paper. Communication complexity asks how much two parties must exchange to compute a joint function. Many measures exist, for different models of the exchange. Following the spirit of the Chomsky hierarchy for grammars, the authors group the measures into classes, but with a new rule for when two measures count as the same.
Two measures are declared constant-equivalent when one stays bounded by a constant exactly for the functions where the other does. That is a much coarser lens than the usual polylogarithmic one. Under it, the authors identify five equivalence classes. The grouping surprises: powerful communication models land in the same class as weak ones. Some seemingly weaker models rise to the top of the hierarchy.
Catalog record
| CREATOR | Andris Ambainis, Hartmut Klauck, Debbie Lim |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 146 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-22004
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Hierarchy for Constant Communication Complexity Andris Ambainis, Hartmut Klauck, Debbie Lim Abstract Similarly to the Chomsky hierarchy, we offer a classification of communication complexity measures such that these measures are organized into equivalence classes. Different from previous attempts of this endeavor, we consider two communication complexity measures as equivalent, if, when one is constant, then the other is constant as well, and vice versa. Most previous considerations of similar topics have been using polylogarithmic input length as a defining characteristic of equivalence. In this paper, two measures 𝒞 1 , 𝒞 2 {\cal C}_{1},{\cal C}_{2} are constant-equivalent , if and only if for all total Boolean (families of) functions f : { 0 , 1 } n × { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\} we have 𝒞 1 ( f ) = O ( 1 ) {\cal C}_{1}(f)=O(1) if and only if 𝒞 2 ( f ) = O ( 1 ) {\cal C}_{2}(f)=O(1) . We identify five equivalence classes according to the above equivalence relation. Interestingly, the classification is counter-intuitive in that powerful models of communication are grouped with weak ones, and seemingly weaker models end up on the top of the hierarchy. 1 Introduction Communication complexity, as a subfield of theoretical computer science emerged from the seminal works of [ 1 , 2 , 3 , 4 ] more than four decades ago. Several other early works include Refs. [ 5 , 6 , 7 ] . In this field, we are able to show lower bound for explicit problems, with a plethora of applications to other computational models such as finite automata, Turing machines, decision trees, ordered binary decision diagrams, VLSI chips, streaming algorithms, networks of threshold gates and data structures [ 8 , 9 , 10 , 2 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 ] . In the theory of formal languages, the Chomsky hierarchy [ 21 ] is a central concept. This hierarchy classifies formal languages according to the type of computational model that can recognize them. The levels of the Chomsky hierarchy can be labelled by a machine model that is able to recognize the languages from the corresponding level, i.e., Finite Automata, Context-Free Grammars, Context-Sensitive Grammars, and Turing Machines (acting as the most powerful formal computation model). The Chomsky hierarchy also classifies formal languages into one of its levels. For instance, the language \{0^{n}1^{n}\} (understood as a family over all n ) is in the class of context-free languages, but not the class of regular languages (as defined by DFA’s). Nondeterministic and deterministic finite automata on the other hand define the same class of regular languages, even though their state-complexity can be exponentially far apart. In this paper, we attempt a similar classification for communication complexity. Technically, communication complexity is usually established for a family of functions \{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\} with all possible input lengths. The complexity of such a family is constant if the needed communication does not increase with the input length. A trivial example of this is the decision if the first bits of Alice’s and Bob’s input are both 1, which a deterministic protocol can decide with 1 bit of communication. A less trivial problem is the Equality function, in which Alice and Bob each receive a string of n bits and their task is to decide whether the two strings are the same. While a deterministic protocol cannot do better than communicating the whole length of a string, a public coin protocol can solve this problem with a single bit of communication and satisfactory error probability. Prior to our work, there have been several studies on establishing hierarchies in communication complexity. In a seminal paper, Babai, Frankl, and Simon [ 3 ] proposed polylogarithmic complexity as the criteria for efficiency and used it to define communication classes analogous to the classical computational complexity classes. Their definition of communication classes provides a structured framework for comparing the powers of various communication models. While this work has undoubtedly led to the development in proving separations between different communication classes, it is also crucial to also consider communication problems that have uniformly bounded complexity. In fact, there is already a line of work on constant-cost communication [ 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 32 ] . These works motivated the work of Hatami and Hatami [ 33 ] , who defined the constant-cost analogues of the communication classes by Babai, Frankl, and Simon [ 3 ] , where the criterion of effectiveness is a O(1) complexity, independent of the input size n . Another related work is that of Göös, Pitassi and Watson [ 34 ] . In their work, the authors outlined the relationships between a wide range of models for two-party communication, clarifying which are stronger, weaker, or incomparable. By establishing new separations and inclusions, they resolves several long-standing open questions and gives a nearly complete structural picture of the complexity landscape in this area. Main contribution. We establish a hierarchy of increasingly powerful classes of communication complexity, based on what these computational models can do with constant communication. While our investigation is based on the constant-equivalence of different measures of communication complexity (for instance nondeterministic and deterministic communication are constant-equivalent), this also leads to a hierarchy of (families of) communication problems. Namely, the problems that can be solved by an equivalence class of communication complexity measure. For instance, the Equality problem is in the class of cheap public coin protocols (see below), while the Greater-Than problem is in the class of low sign-rank protocols [ 25 ] . We identify the following levels of our hierarchy, named here by the simplest way to define them (more details in Figure 1 ): • Class 1: Only a constant number of distinct rows in the communication matrix. • Class 2: The \gamma_{2} norm of the communication matrix is constant. • Class 3: The approximate \gamma_{2} norm, \gamma_{2}^{\alpha} , of the communication matrix is constant which implies that information complexity and also the commonly used randomized/quantum communication complexity lower bounds such as the rectangle bound (with error) and the discrepancy bound are also constant. • Class 4: The sign-rank and the (truly) unbounded error communication complexity are constant. • Class 5: Measures defined in terms of product-distribution communication complexity are constant. We provide equivalence results for all the measures in the respective classes, and separating functions for the different levels of the hierarchy. While most of this work is collecting existing results, we have the following new results: Result 1 . Let f be a total Boolean function and denote by R^{\operatorname{pub}}_{\epsilon}(f) the public-coin randomized communication complexity with oblivious and exact error (see Section 3.2 ). Then we have \log\gamma_{2}\leq R^{\operatorname{pub}}_{=\epsilon}(f)\leq O((\gamma_{2}(f))^{2}). Result 2 . Let HD_{1}:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\} be a function that returns 1 if the Hamming distance between x,y\in\{0,1\}^{n} is 1 and returns 0 otherwise. We have \gamma_{2}(HD_{1})=\Theta(\sqrt{n}). We summarize our results in Figure 1 . Class 5 D^{[]}_{\epsilon}(f) , D^{A\rightarrow B,[]}_{\epsilon}(f) , R^{A\rightarrow B,[]}_{\epsilon}(f) , Q^{A\rightarrow B,[]}_{\epsilon}(f) , \operatorname{rec}^{A\rightarrow B,[]}_{\epsilon}(f)