Direct Sum Theorems From Fortification
摘要
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 [1] 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 [3] 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 \textsf{Cov}\left( S\times T\right) \ge \log \textsf{Cov}\left( S\right) + \log \textsf{Cov}(T) -\log \log |P||Q|-4\) , where \(\textsf{Cov}\) denotes the cover number. One issue of current deterministic direct sum theorems [2, 3] 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 \(\textsf{L}\) denotes complexity of the protocol size of a communication problem, given a communication problem \(F:A \times B \rightarrow \{0,1\}\) , \(\log \textsf{L}\left( F\times F\right) \ge \log \textsf{L}\left( F\right) +\varOmega \left( \sqrt{\log \textsf{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.