Direct Sum Theorems From Fortification

Hao Wu

TL;DR

This paper provides a new approach to "direct sum" problems in communication complexity by generalizing the concept of fortification. By introducing a dual form of the cover number called a $\delta$-fooling set, the author proves a new direct sum theorem for protocol size that remains meaningful even for just two copies of a problem ($n=2$), addressing a significant gap in existing deterministic direct sum theorems.

What Problem Does This Paper Address?

In communication complexity, the direct sum question asks: is the resource (like bits of communication or protocol size) needed to solve $n$ independent problems together roughly equal to the sum of the resources needed to solve them separately?

While we have theorems for large $n$, they often fall apart when $n$ is small. For example, if solving one copy of a function $F$ requires $C(F)$ bits, existing theorems might only show that solving two copies requires $\Omega(2 \cdot \sqrt{C(F)})$ bits. If $C(F)$ is small, this lower bound might be lower than the cost of solving just one copy!

The author seeks to prove that solving two copies of a problem is strictly harder than solving one, specifically focusing on measures like cover number (the minimum number of rectangles needed to cover a function's input) and protocol size (the number of leaves in a communication tree).

Methods

The core of the paper is the generalization of the Fortification Lemma originally proposed by Dinur and Meir (2018).

  1. General Fortification: The author observes that fortification is a property of any sub-additive measure over a set. They prove a general lemma stating that for any such measure, there exists a "fortified" subset where the measure of any large enough sub-subset is proportional to its density.
  2. The $\delta$-fooling set: By applying this general lemma to the "cover number" measure, the author derives the $\delta$-fooling set. This is a generalized version of a standard fooling set. In a $\delta$-fooling set, any subset larger than a certain fraction $\delta$ cannot be covered by a single monochromatic rectangle.
  3. Hardcore Construction: To prove direct sum theorems, the author uses these $\delta$-fooling sets to construct a "hardcore" for the combined problem. This hardcore is a collection of inputs that are guaranteed to be difficult to solve simultaneously, allowing for a simple double-counting argument to establish lower bounds.

Datasets

As a theoretical paper in computational complexity, no empirical datasets were used. The work is based on mathematical proofs and builds upon standard communication complexity models.

Key Insights and Ideas

  • Fortification is Universal: The realization that fortification isn't just for protocol size but applies to any sub-additive measure (like entropy or cover number) is a powerful abstraction.
  • Duality of Cover Number: The $\delta$-fooling set acts as a "dual" to the cover number. If a problem has a high cover number, it must contain a $\delta$-fooling set. This provides a concrete combinatorial structure to work with when proving lower bounds.
  • Breaking the $n=2$ Barrier: By using the $\delta$-fooling set to find a "hardcore," the author can show that solving $F \times F$ requires an additive boost in complexity ($+\Omega(\sqrt{\log L(F)})$) rather than just a multiplicative factor that might be trivial for small $n$.

Key Results

  • Cover Number Direct Sum: The paper provides a simpler proof for the classic direct sum theorem for cover numbers: $$\log \mathsf{Cov}(S \times T) \geq \log \mathsf{Cov}(S) + \log \mathsf{Cov}(T) - \log \log |P||Q| - 4$$
  • Protocol Size Direct Sum: The main new result is a stronger theorem for protocol size ($L$): $$\log \mathsf{L}(F \times F) \geq \log \mathsf{L}(F) + \Omega(\sqrt{\log \mathsf{L}(F)}) - \log \log |A||B| - 4$$ This confirms that for any sufficiently complex function $F$, solving two copies is strictly harder than solving one.

Limitations and Future Work

  • Communication Complexity ($C$): The author notes that their approach works well for protocol size ($L$) because it is highly structural and sub-additive. However, it does not directly translate to communication complexity ($C$), which is less structural. Proving a similar "boost" for $C(F \times F)$ remains an open conjecture.
  • Randomized Complexity: The paper suggests that while the fortification lemma works if you relax the definition of a rectangle cover (to "nearly monochromatic" rectangles), it is currently unknown if a small cover of nearly monochromatic rectangles implies small randomized communication complexity.
  • Other Measures: The author suggests that other sub-additive measures, such as entropy (H), could be fortified using this general framework, potentially leading to new applications in information theory.

Summary updated

Abstract

We revisit the direct sum questions in communication complexity which asks whether the resource needed to solve $n$ communication problems together is (approximately) the sum of resources needed to solve these problems separately. Our work starts with the observation that Dinur and Meir's fortification lemma can be generalized to a general fortification lemma for a sub-additive measure over set. By applying this lemma to the case of cover number, we obtain a dual form of cover number, called "$δ$-fooling set" which is a generalized fooling set. Any rectangle which contains enough number of elements from a $δ$-fooling set can not be monochromatic. With this fact, we are able to reprove the classic direct sum theorem of cover number with a simple double counting argument. Formally, let $S \subseteq (A\times B) \times O$ and $T \subseteq (P\times Q) \times Z$ be two communication problems, $ \log \mathsf{Cov}\left(S\times T\right) \geq \log \mathsf{Cov}\left(S\right) + \log\mathsf{Cov}(T) -\log\log|P||Q|-4.$ where $\mathsf{Cov}$ denotes the cover number. One issue of current deterministic direct sum theorems about communication complexity is that they provide no information when $n$ is small, especially when $n=2$. In this work, we prove a new direct sum theorem about protocol size which imply a better direct sum theorem for two functions in terms of protocol size. Formally, let $\mathsf{L}$ denotes complexity of the protocol size of a communication problem, given a communication problem $F:A \times B \rightarrow \{0,1\}$, $ \log\mathsf{L}\left(F\times F\right)\geq \log \mathsf{L}\left(F\right) +Ω\left(\sqrt{\log\mathsf{L}\left(F\right)}\right)-\log\log|A||B| -4$. All our results are obtained in a similar way using the $δ$-fooling set to construct a hardcore for the direct sum problem.
BibTeX
@misc{wu2022direct,
  author = {Hao Wu},
  title = {{Direct Sum Theorems From Fortification}},
  year = {2022},
  eprint = {2208.07730},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.07730},
}
Figure