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).
- 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.
- 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.
- 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