Lower bounds on communication complexity
Lower bounds on communication complexity
复制标题
通信复杂性的下限
DOI：
10.1145/800057.808668
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
G. Schnitger
中科院分区：
文献类型：
--
作者：
P. Duris;Z. Galil;G. Schnitger
我们证明了以下四个关于通信复杂性的结果：
1)对于每一个k ≥ 2，包含从第一个顶点到最后一个顶点的长度为k+1的路径并且可以通过使用简单的k轮协议交换O（k log n）位来识别的出度1的有向图的编码语言L<subscrpt>k</subscrpt>需要交换Ω（n<supscrpt>1/2</supscrpt>/k<supscrpt>4</supscrpt> log<supscrpt>3</supscrpt> n）位，如果使用任何（k−1）轮协议。
2)对于每个k ≥ 1和无穷多个n ≥ 1，存在一个集合L<supscrpt>n</supscrpt><subscrpt>k</subscrpt> @ {0，1}<supscrpt>2n</supscrpt>，可以通过使用k轮协议交换O（k log n）位来识别，并且任何识别L<supscrpt>n</supscrpt><subscrpt>k的</subscrpt>（k−1）轮协议都需要交换Ω（n/k）位。
3)给定集合L @ {0，1}<supscrpt>2n</supscrpt>，存在集合L@{0，1}<supscrpt>8 n</supscrpt>，使得识别L@的任何（k轮）协议可以被变换为具有<underline>相同</underline>通信复杂度的识别L的（k轮）<underline>固定分区</underline>协议，反之亦然。
4)对于每个整数函数f，1 ≤f（n）≤ n，存在通过交换f（n）位<underline>的一轮</underline>确定性协议识别的语言，但不能通过交换f（n）-1位的任何<underline>非确定性</underline>协议识别。
前两个结果以无与伦比的方式显示了（k-1）轮和k轮协议之间的指数差距，解决了Papadimitriou和Sipser的猜想。第三个结果表明，只要我们对存在性证明感兴趣，输入的固定划分就不是限制。第四个结果扩展了Papadimitriou和Sipser的结果，他们证明了对于每个整数函数f，1 ≤ f（n）≤ n，存在一种语言被交换f（n）位的确定性协议接受，但不被任何交换f（n）− 1位<underline>的确定性</underline>协议接受。
We prove the following four results on communication complexity:
1) For every k ≥ 2, the language L<subscrpt>k</subscrpt> of encodings of directed graphs of out degree one that contain a path of length k+1 from the first vertex to the last vertex and can be recognized by exchanging O(k log n) bits using a simple k-round protocol requires exchanging Ω(n<supscrpt>1/2</supscrpt>/k<supscrpt>4</supscrpt>log<supscrpt>3</supscrpt>n) bits if any (k−1)- round protocol is used.
2) For every k ≥ 1 and for infinitely many n ≥ 1, there exists a collection of sets L<supscrpt>n</supscrpt><subscrpt>k</subscrpt> @@@@ {0,1}<supscrpt>2n</supscrpt> that can be recognized by exchanging O(k log n) bits using a k-round protocol, and any (k−1)-round protocol recognizing L<supscrpt>n</supscrpt><subscrpt>k</subscrpt> requires exchanging Ω(n/k) bits.
3) Given a set L @@@@ {0,1}<supscrpt>2n</supscrpt>, there is a set L@@@@{0,1}<supscrpt>8n</supscrpt> such that any (k-round) protocol recognizing L@@@@ can be transformed to a (k-round) <underline>fixed partition</underline> protocol recognizing L with the <underline>same</underline> communication complexity, and vice versa.
4) For every integer function f, 1 ≤f(n) ≤ n, there are languages recognized by a <underline>one round</underline> deterministic protocol exchanging f(n) bits, but not by any <underline>nondeterministic</underline> protocol exchanging f(n)−1 bits.
The first two results show in an incomparable way an exponential gap between (k−1)-round and k-round protocols, settling a conjecture by Papadimitriou and Sipser. The third result shows that as long as we are interested in existence proofs, a fixed partition of the input is not a restriction. The fourth result extends a result by Papadimitriou and Sipser who showed that for every integer function f, 1 ≤ f(n) ≤ n, there is a language accepted by a deterministic protocol exchanging f(n) bits but not by any <underline>deterministic</underline> protocol exchanging f(n) − 1 bits.