On the complexity of communication complexity
On the complexity of communication complexity
复制标题
论通信的复杂性
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Enav Weinreb
中科院分区：
文献类型：
--
作者：
E. Kushilevitz;Enav Weinreb
我们考虑以下问题：给定一个双参数布尔函数f，用N x N二进制矩阵表示，确定f的（确定性）通信复杂度有多难？我们处理这个问题的两个方面。在计算方面，我们证明，在适当的密码学假设下（例如因式分解的难解性），f的确定性通信复杂性很难在某个常数内近似。在更强的（但可以说是合理的）假设下，我们得到更强的硬度结果，与最已知的近似相匹配。在解析方面，我们给出了一组（双参数）函数，对于这些函数，确定确定性通信复杂度（甚至获得其非平凡下界）意味着证明一些相关函数的电路下界。电路复杂性和通信复杂性之间的这种联系以前是已知的（Karchmer &#; Wigderson, 1988），只是在关系的更复杂的背景下（搜索问题），而不是在函数的背景下（决策问题）。特别是，这一结果可以解释分析某些函数的通信复杂性的困难，例如Yannakakis（1988）引入的“集团与独立集”函数族。
We consider the following question: given a two-argument boolean function f, represented as an N x N binary matrix, how hard is it to determine the (deterministic) communication complexity of f? We address two aspects of this question. On the computational side, we prove that, under appropriate cryptographic assumptions (such as the intractability of factoring), the deterministic communication complexity of f is hard to approximate to within some constant. Under stronger (yet arguably reasonable) assumptions, we obtain even stronger hardness results that match the best known approximation. On the analytic side, we present a family of (two-argument) functions for which determining the deterministic communication complexity (or even obtaining non-trivial lower bounds on it) implies proving circuit lower bounds for some related functions. Such connections between circuit complexity and communication complexity were known before (Karchmer &#; Wigderson, 1988) only in the more involved context of relations (search problems) but not in the context of functions (decision problems). This result, in particular, may explain the difficulty of analyzing the communication complexity of certain functions such as the "clique vs. independent-set" family of functions, introduced by Yannakakis (1988).