Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

Vladimir V. Podolskii, Alexander A. Sherstov

Abstract

For decades, a "logarithmic barrier" has limited our understanding of communication complexity in the "number-on-the-forehead" (NOF) model, specifically when the number of players $k$ exceeds $\log n$. This paper breaks this barrier for two fundamental problems: Generalized Inner Product (GIP) and Set Disjointness (DISJ). By employing a novel "silent player" reduction and analytical techniques involving polynomial approximation, the authors establish a tight, superconstant lower bound of $\Theta\left(\frac{\log n}{\log(1 + k/\log n)} + 1\right)$ for any $k \ge \log n$. These results demonstrate that for these specific problems, interaction provides no asymptotic advantage over simultaneous broadcast protocols, and they provide the first non-trivial lower bounds for explicit functions in this high-player regime.

Introduction

In theoretical computer science, communication complexity measures the amount of information exchange required for multiple parties to compute a function when the input is distributed among them. The number-on-the-forehead (NOF) model is particularly challenging: imagine $k$ players where each player $i$ has an input $x_i$ written on their forehead. Every player can see all inputs except their own. This high degree of information overlap makes proving lower bounds—showing that a problem is "hard"—notoriously difficult.

Historically, researchers could only prove strong lower bounds for $k < \log n$ players. Once the number of players reached or exceeded the logarithm of the input size $n$, existing techniques like the standard discrepancy method failed to yield superconstant results. This paper addresses this long-standing gap, focusing on the Generalized Inner Product (GIP) and Set Disjointness (DISJ) functions.

Problem Definitions

The authors investigate two core Boolean functions in the NOF setting:

  1. Generalized Inner Product (GIP): The function outputs 1 if the number of bitwise indices where all $k$ players have a '1' is odd, and 0 otherwise.
  2. Set Disjointness (DISJ): The function outputs 1 if there is at least one index where all $k$ players have a '1', and 0 otherwise.

Both problems are central to complexity theory, serving as benchmarks for the limits of distributed computation and information theory.

Methodology

The paper's findings rely on a combination of combinatorial reductions and analytical tools:

The Silent Player Reduction

A primary technical contribution is the "silent player" insight. The authors observe that in any protocol with low communication (e.g., $O(\log n)$ bits), the vast majority of the $k$ players must remain silent during any specific execution. By identifying a subset of "active" players and reducing the $k$-player game to a smaller, more manageable version, the authors can apply lower bound techniques that were previously restricted to the $k < \log n$ regime.

Polynomial Approximation and Discrepancy

For Set Disjointness, the authors utilize the relationship between communication complexity and the approximate degree of Boolean functions. This involves determining the minimum degree of a polynomial that closely approximates the function. Additionally, they refine the discrepancy method, which bounds the correlation between a function and simple communication patterns, to show that GIP remains hard even as $k$ grows.

Simultaneous vs. Interactive Protocols

To establish the upper bounds, the authors adapt deterministic protocols (notably those by Grolmusz) into the randomized setting. They show that players can achieve the optimal communication rate by broadcasting a single message simultaneously, without needing to wait for or respond to other players' messages. This reveals that interaction does not provide an asymptotic benefit for GIP and DISJ when $k \ge \log n$.

Key Results

The central result of the paper is the derivation of a tight bound for the randomized communication complexity of both GIP and DISJ for all $k \ge \log n$:

$$\Theta\left(\frac{\log n}{\log(1 + k/\log n)} + 1\right)$$

This formula has several significant implications:

  • Breaking the Barrier: It provides the first superconstant lower bound for any explicit problem in the NOF model where $k$ is significantly larger than $\log n$.
  • The Threshold of Easiness: The results indicate that these problems only become "easy" (requiring $O(1)$ communication) when the number of players is extremely large, specifically $k \ge n^\epsilon$ for some constant $\epsilon > 0$.
  • Optimality: Because the authors provide both a lower bound and a matching upper bound, the complexity of these functions is now fully characterized in this regime.

Conclusion and Future Work

By shattering the logarithmic barrier for GIP and DISJ, this work provides a new roadmap for NOF communication complexity. However, significant challenges remain. The "holy grail" of this field is proving even stronger lower bounds (such as $n^{\Omega(1)}$) for $k = \log n$ players. Such a result would have profound implications for circuit complexity, potentially leading to the first super-polynomial lower bounds for the complexity class $ACC^0$. While this paper focuses on specific functions, the techniques introduced—particularly the silent player reduction—may prove instrumental in tackling more general classes of functions in the future.

Summary updated

BibTeX
@article{podolskii2020inner,
  author = {Vladimir V. Podolskii and Alexander A. Sherstov},
  title = {{Inner Product and Set Disjointness: Beyond Logarithmically Many Parties}},
  journal = {ACM Trans. Comput. Theory},
  year = {2020},
  doi = {10.1145/3428671},
}
Figure