Abstract
In this work we introduce, both for classical communication complexity and query complexity, a modification of the 'partition bound' introduced by Jain and Klauck [2010]. We call it the 'public-coin partition bound'. We show that (the logarithm to the base two of) its communication complexity and query complexity versions form, for all relations, a quadratically tight lower bound on the public-coin randomized communication complexity and randomized query complexity respectively.
Introduction
In theoretical computer science, determining the fundamental limits of computation is a central challenge. Researchers typically measure this through two lenses: Communication Complexity, which quantifies the information exchange required between two parties (Alice and Bob) to solve a puzzle, and Query Complexity, which counts how many bits of a hidden input a computer must examine to find an answer.
For over a decade, the partition bound (introduced in 2010) served as one of the most robust methods for proving "lower bounds"—the mathematical proof that a problem requires at least a certain amount of resources. However, the precision of this bound remained uncertain. It was unknown whether the bound was a near-perfect reflection of computational reality or if a significant gap existed between the bound and actual difficulty. This paper closes that gap by refining the partition bound into a version that is provably close to true complexity.
The Public-Coin Partition Bound
The authors introduce a modification to the existing framework called the public-coin partition bound ($pprt$).
Standard partition bounds are formulated using Linear Programs (LPs), which search for a weighted collection of "rectangles" (sets of inputs) that cover a problem's domain. The core innovation of this work lies in adding a specific structural constraint to the LP: the weights must correspond to a probability distribution over actual partitions of the input space.
This is a critical distinction because a randomized protocol is essentially a probability distribution over deterministic protocols, which themselves function as partitions. By forcing the mathematical bound to mirror this algorithmic structure, the authors ensure the bound behaves like a real-world protocol. Using the dual of these linear programs, the paper demonstrates that the optimal value of this LP is inextricably linked to the actual number of bits or queries required to solve a relation.
Key Insights and Ideas
- The Power of Partitions: The original partition bound was often "loose" because it allowed for overlapping rectangles. By requiring the bound to be a convex combination of partitions—where every input belongs to exactly one rectangle—the authors align the mathematics with the actual execution of communication protocols.
- LP as a Universal Yardstick: The research reinforces the idea that Linear Programming is a premier method for characterizing complexity. If a problem's constraints can be captured within an LP, its fundamental limits can often be identified.
- Bridging the Gap: The most significant finding is that the logarithm of this new bound is not just a lower bound, but its square acts as an upper bound. In the context of complexity theory, this "quadratic" relationship is considered exceptionally tight.
Main Results
The authors prove two primary theorems that apply to any relation $f$ and error tolerance $\epsilon$:
- Communication Complexity: They show that the public-coin randomized communication complexity ($R^{pub}$) is bounded between the log of the $pprt$ bound and the square of that log.
- Lower Bound: $\log_2 pprt_\epsilon(f) \leq R^{pub}_\epsilon(f)$
- Upper Bound: $R^{pub}_{2\epsilon}(f) \leq (\log_2 pprt_\epsilon(f) + O(1))^2$
- Query Complexity: A parallel result holds for randomized query complexity ($R_\epsilon$), proving that the number of bits a computer needs to read is also quadratically related to the $pprt$ bound.
- Comparative Strength: The authors demonstrate that this new public-coin bound is strictly stronger than the original 2010 partition bound for all relations, providing a more accurate tool for the field.
Limitations and Future Work
While "quadratically tight" represents a major theoretical leap, it is not yet "linearly tight." A gap remains due to the squaring of the term, and a major open question is whether a bound exists that can characterize complexity within a constant factor. Additionally, the paper notes that the relationship between the partition bound and information complexity (a measure based on Shannon entropy) remains an intriguing mystery that warrants further investigation.
Reference: Jain, R., Lee, T., & Vishnoi, N. K. (2014). A quadratically tight partition bound for classical communication complexity and query complexity. arXiv:1401.4512v1.
Summary updated