Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-114 | 14th October 2023 04:57

Direct Sum Theorems From Fortification

RSS-Feed




Revision #1
Authors: Hao Wu
Accepted on: 14th October 2023 04:57
Downloads: 133
Keywords: 


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 ``$\delta$-fooling set'' which is a generalized fooling set. Any rectangle which contains enough number of elements from a $\delta$-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) +\Omega\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 $\delta$-fooling set to construct a hardcore for the direct sum problem.



Changes to previous version:

fix some typos; remove a section of agree problem with a gap in the proof pointed by an anonymous reviewer, the author has tried to fix it but could not fix it for now.


Paper:

TR22-114 | 16th August 2022 16:00

Direct Sum Theorems From Fortification





TR22-114
Authors: Hao Wu
Publication: 16th August 2022 16:21
Downloads: 404
Keywords: 


Abstract:

We revisit the direct sum theorems in communication complexity which askes whether the resource to solve $n$ communication problems together is (approximately) the sum of resources to solve these problems separately. Our work starts with the observation that Meir and Dinur's fortification lemma for protocol size over rectangles 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 ``$\delta$-fooling set'' which is a generalized fooling set. Given a communication problem $S\subseteq (X\times Y) \times Z$, let $\Lambda \subseteq X\times Y$ be a $\delta$-fooling set of $S$, then given any subset $\tilde{\Lambda} \subseteq \Lambda$ such that $|\tilde{\Lambda}|/{|\Lambda|} > \delta$, there is no monochromatic rectangle that covers the subset $\tilde{\Lambda}$. Particularly, there is a $\frac{16\log|X| |Y|}{{Cov}(S)}$-fooling set of communication problem $S$.

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 {Cov}\left(S\times T\right)
\geq \log{Cov}\left(S\right)
+ \log{Cov}(T)
-\log\log|P||Q|-4.$ where ${Cov}$ denotes the cover number.

One issue of current deterministic direct sum theorems about commutation complexity or protocol size 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 ${L}$ denote the protocol size, given a communication problem $F:A \times B \rightarrow
\{0,1\}$, $
\log{L}\left(F\times F\right)\geq
\log {L}\left(F\right) +\Omega\left(\sqrt{\log{L}\left(F\right)}\right)-\log\log|A||B| -4$.

We also address other direct sum type problem such like the agree problem introduced by Amos Beimel et. We prove a tight cover number lower bound for the agree problem. Formally, let $S_i \subseteq X_i \times Y_i \times Z, i\in [k]$ be $k$ two-party communication problems,
${Cov}
\left({agree}(S_1,\ldots,S_k)\right) \geq \min_{i\in [k]}
\left\{ \frac{{Cov}(S_i)}{16\log|X_i| |Y_i|} \right\}.
$

All our direct sum type results are obtained in a similar way, that is using the $\delta$-fooling set to construct a hardcore for the direct sum type problem.



ISSN 1433-8092 | Imprint