A note on the partition bound for one-way classical communication complexity

Srinivasan Arunachalam, João F. Doriguello, Rahul JainarXiv 2023 · DOI · arXiv

Abstract

This paper investigates the "one-way partition bound," a linear programming-based tool for characterizing one-way randomized communication complexity. By establishing a reciprocal relationship between this bound and one-way zero-communication efficiency, the authors demonstrate that the partition bound provides a remarkably tight characterization. Specifically, they reduce the error gap from a logarithmic term to a double-logarithmic term, $\log \log(1/\delta)$, for any partial function $f$.

Introduction

In communication complexity, the fundamental question is: "What is the minimum number of bits Alice must send to Bob to compute a function $f(x, y)$?" In the one-way model, Alice sends a single message, and Bob outputs the result. To establish lower bounds on this communication, researchers use various mathematical recipes. The partition bound, which covers the input space with rectangles where the function is constant, is known to be powerful for general two-way communication. However, its tightness in the one-way setting required further refinement. Previously, the best characterization used the rectangle bound, leaving an additive error term of $O(\log(1/\delta))$. This work aims to shrink that gap.

Methods

The authors define the one-way partition bound ($\text{prt}^1_\epsilon(f)$) using Linear Programming (LP). They construct a Primal LP to minimize weights over sets of inputs and a corresponding Dual LP.

The Primal and Dual Linear Programs defining the one-way partition bound.

The core of the proof relies on the concept of one-way zero-communication efficiency ($\text{eff}^1_\epsilon$). In this model, Alice and Bob share randomness but cannot communicate; Alice either sends a "success" signal or "aborts." A key insight (Lemma 3) is that the one-way partition bound is exactly the reciprocal of this zero-communication efficiency ($1/\text{eff}^1_\epsilon$). By simulating randomized one-way protocols as zero-communication protocols and vice versa, the authors derive tight upper and lower bounds for communication complexity.

Key Results

The primary contribution is Theorem 1, which relates one-way randomized communication complexity ($R^1_\epsilon(f)$) to the partition bound:

  • Lower Bound: $R^1_\epsilon(f) \ge \log \text{prt}^1_\epsilon(f)$.
  • Upper Bound: $R^1_{\epsilon+\delta}(f) \le \log \text{prt}^1_\epsilon(f) + \log \log(1/\delta)$.

This shows that the partition bound is a near-perfect proxy for communication complexity. The shift from a $\log(1/\delta)$ to a $\log \log(1/\delta)$ error term represents a significant theoretical improvement. Furthermore, this characterization is universal, holding for every partial function $f$.

Conclusion

While this work focuses on classical one-way communication with shared randomness, it sets a high bar for tightness in complexity bounds. The results suggest that the partition bound captures the essence of one-way communication almost perfectly. Future work may explore similar refinements for quantum partition bounds or private randomness settings.

Summary updated

BibTeX
@misc{arunachalam2023note,
  author = {Srinivasan Arunachalam and João F. Doriguello and Rahul Jain},
  title = {{A note on the partition bound for one-way classical communication complexity}},
  year = {2023},
  eprint = {2302.10431},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.10431},
}

Loading related content...

Figure