The Communication Complexity of Functions with Large Outputs

Lila Fontes, Sophie Laplante, Mathieu Laurière, Alexandre Nolin

Abstract

Traditional communication complexity focuses on Boolean functions where the output is a single bit. However, many real-world and theoretical problems involve $k$-bit outputs. This paper investigates the communication cost of such functions, demonstrating that the standard requirement for the transcript to reveal the output introduces a $k$-bit overhead that is often unnecessary. By introducing a hierarchy of output models—culminating in the highly efficient XOR model—the authors show that fundamental operations like error reduction and derandomization can be performed with significantly lower communication costs than previously thought.

Introduction

In the classical two-party communication model, Alice and Bob receive inputs $x$ and $y$ respectively and wish to compute a function $f(x, y)$. The "cost" of a protocol is typically measured by the number of bits exchanged. A standard implicit assumption is that the protocol's transcript must allow an external observer to determine the output.

While this assumption is trivial for Boolean functions, it becomes a bottleneck for functions with $k$-bit outputs. If the logic of the function requires only $c$ bits of communication, but the output itself is $k$ bits, the total cost becomes $c + k$. This $k$-bit overhead can dwarf the actual complexity of the computation. This paper asks: what is the "true" communication complexity of a problem when we relax the requirement of how the output is revealed?

A Hierarchy of Output Models

The authors define six distinct models for how Alice and Bob can "output" a $k$-bit string, ordered from most restrictive to most flexible:

  1. Open: An external observer can determine the output solely from the transcript.
  2. Local: Both Alice and Bob know the output at the end, but an observer might not.
  3. Unilateral: One designated player (e.g., Alice) learns the output.
  4. One-out-of-two: At least one player learns the output, but the protocol doesn't specify which one.
  5. Split: The $k$ bits are divided; Alice knows some bits, Bob knows the rest.
  6. XOR: Alice outputs a string $a$ and Bob outputs $b$ such that the final result is $a \oplus b$.

The XOR model is particularly significant. Inspired by quantum XOR games, it allows the output to be completely hidden from an external observer and even from the individual players. This model represents the most efficient way to "compute" a result without necessarily "revealing" it.

Methodological Innovations

To analyze these models, the authors employ several sophisticated theoretical tools:

  • Gap Majority composed with XOR (GapMAJ $\circ$ XOR): This novel problem serves as a building block for achieving error reduction in models where players do not know the intermediate results of the protocol.
  • Random Graph Theory: The researchers use Erdős-Rényi random graph properties to identify clusters of protocol runs. This allows them to prove that certain outputs can be reached without the transcript explicitly revealing the bits.
  • Rank-based Lower Bounds: The authors adapt the classic monochromatic rectangle argument. In these new models, the rectangles in the communication matrix are not necessarily solid but may be "striped," varying systematically by row or column.

Key Results and Insights

1. Model Separation

The authors formally prove that these six models are distinct. For specific problems, the communication cost drops significantly as one moves down the hierarchy, confirming that the method of output delivery is a fundamental component of complexity.

2. Error Reduction in the XOR Model

Standard error reduction involves running a protocol multiple times and taking a majority vote. In the XOR model, this is non-trivial because neither player knows the individual results. The authors overcome this using Theorem 5.3, which demonstrates that error can be reduced with only $O(1)$ additional communication relative to $k$. They achieve this by using Equality tests on pairs of protocol runs to identify agreement without revealing the strings themselves.

3. Efficient Derandomization

Converting a randomized protocol to a deterministic one usually incurs a cost exponential in the output length ($2^k$). Theorem 6.4 shows that for the XOR model, this cost can be reduced to $O(2^R \cdot k)$, where $R$ is the randomized complexity. This linear dependency on $k$ is a massive improvement over naive methods.

4. Lower Bounds

The paper establishes that the rank of the communication matrix still provides a viable lower bound for these relaxed models: $D^{xor}(f) \geq \log \text{rank}(M_f) - \log(k+1)$. This provides a tool for proving that even in the most flexible models, certain problems remain inherently difficult.

Discussion and Future Work

While this work provides a robust framework for functions, the authors note that relations (where multiple outputs are valid) may behave differently. Additionally, while they conjecture that their deterministic upper bound for the Gap Majority problem is tight ($\Omega(Nk)$), a formal lower bound remains an open challenge. Finally, given the XOR model's roots in quantum theory, exploring quantum communication complexity within this hierarchy is a promising next step for the field.

Summary updated

BibTeX
@inproceedings{fontes2023communication,
  author = {Lila Fontes and Sophie Laplante and Mathieu Laurière and Alexandre Nolin},
  title = {{The Communication Complexity of Functions with Large Outputs}},
  booktitle = {SIROCCO},
  year = {2023},
  doi = {10.1007/978-3-031-32733-9\_19},
}
Figure