TL;DR
This paper offers a more elegant proof of Newman's theorem, a cornerstone of communication complexity. By leveraging geometric insights from Carathéodory's theorems, the authors provide a cleaner derivation of how public randomness offers only a logarithmic advantage over private randomness in communication tasks.
What Problem Does This Paper Address?
Communication complexity studies the minimum amount of communication required for two parties (Alice and Bob) to compute a function, given their private inputs. A key question is how much communication cost can be reduced by allowing Alice and Bob to use shared randomness (public randomness) compared to only using their own private randomness. Newman's theorem, a fundamental result in this area, states that public randomness provides at most a logarithmic improvement in communication cost over private randomness. The standard proofs of this theorem often rely on probabilistic methods and concentration inequalities (like the Chernoff bound). This paper aims to provide an alternative, more geometric proof of Newman's theorem by directly applying powerful results from convex geometry, specifically Carathéodory's theorems.
Methods
The core of this paper's contribution lies in its proof technique. Instead of relying on probabilistic methods, the authors frame the problem in terms of convex geometry. They represent the set of deterministic protocols for a function as points in a high-dimensional space. The average of these protocols, which corresponds to a randomized protocol, can then be viewed as a point within the convex hull of these deterministic protocols.
The proof hinges on two key geometric theorems:
- Carathéodory's Theorem (Classical): This theorem states that any point in the convex hull of a set of points in $n$-dimensional space can be expressed as a convex combination of at most $n+1$ points from the original set.
- Approximate Carathéodory's Theorem: This is a more recent extension that states for any point in the convex hull of a set of points (under certain boundedness conditions), there exists a point close to it that can be expressed as a convex combination of a much smaller number of points, specifically $O(\log |S| / \delta)$ points, where $\delta$ is the desired approximation accuracy.
By applying these theorems, the authors show that a randomized protocol (which can be seen as a point in a convex hull) can be approximated by a protocol that is a convex combination of a significantly smaller number of deterministic protocols. This reduction in the number of constituent deterministic protocols, when translated back to the communication complexity setting, leads to the logarithmic advantage of public randomness.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Geometric Perspective on Communication Complexity: The paper beautifully illustrates how abstract concepts in communication complexity can be elegantly captured and proven using fundamental geometric principles. This suggests a broader potential for applying convex geometry to other problems in theoretical computer science.
- Carathéodory's Theorems as Powerful Tools: The proof highlights the practical utility of Carathéodory's theorems, particularly the approximate version, in deriving non-trivial results in complexity theory. It shows that these theorems can provide more direct and perhaps more intuitive proofs than probabilistic methods.
- "Neater" Proof: The authors suggest their proof is "neater," implying a gain in clarity and conceptual simplicity by avoiding the machinery of probabilistic bounds. This can be invaluable for understanding and teaching these concepts.
Key Results
The paper provides a new proof for Newman's theorem, which states that for any Boolean function $f$, the communication cost using private randomness ($R_{pri}$) is bounded by the communication cost using public randomness ($R_{pub}$) plus a logarithmic term:
$R_{pri}(f) < R_{pub}(f) + O(\log n + \log \delta^{-1})$
where $n$ is the input size and $\delta$ is the error parameter. The proof demonstrates that the $O(\log n)$ term arises naturally from the application of Carathéodory's theorems.
Limitations and Future Work
The authors acknowledge that their proof is "not too different from the standard proof" in its reliance on a similar method for proving the approximate Carathéodory theorem. However, they emphasize that the geometric approach offers a "neater" alternative.
The paper also hints at future work by stating, "presenting such a new proof may induce new applications." This suggests that the geometric perspective might be applicable to other problems in communication complexity or related fields where similar trade-offs between randomness and communication are explored. The connection between approximate Carathéodory theorems and computer science applications is noted as an area with ongoing discussion.
Summary updated