论文标题
通讯纪念品：无内存的沟通复杂性
Communication memento: Memoryless communication complexity
论文作者
论文摘要
我们研究计算功能的通信复杂性$ f：\ {0,1 \}^n \ times \ {0,1 \}^n \ rightarrow \ rightArrow \ {0,1 \} $在内存通信模型中。在这里，Alice在\ {0,1 \}^n $中给出了$ x \，bob in \ {0,1 \}^n $ in \ y \ in \ y \ in \ y \ in \ y \ in \ {0,1 \}^n $，他们的目标是计算f（x，y）受到以下约束的约束：在每个回合中，爱丽丝（Alice）在鲍勃（Bob）上收到了鲍勃（Bob）的消息，她的答复完全依赖于鲍勃（Bob）的答复，完全依赖于消息接收到的消息和她的input x;鲍勃也是如此。在此模型中，计算F的成本是爱丽丝和鲍勃之间任何一轮交换的最大位数（在最坏情况下输入X，y）。在本文中，我们还考虑了我们的无内存模型的变体，其中允许其中一个方有内存，允许各方传达量子位，只允许一个玩家发送消息。我们表明，我们的无内存通信模型捕获了Buhrman等人的园林 - 园艺模型。 （ITCS'13），Brody等人的空间有限通信复杂性。 （ITCS'13）和Papakonstantinou等人的覆盖沟通复杂性。 （CCC'14）。因此，无内存的通信复杂性模型为研究了空间结合的通信模型提供了一个统一的框架。我们确定以下内容：（1）我们表明，f的无内存通信复杂性等于最小的两部分分支程序计算F的对数（最高为2）； （2）我们表明，无内存的沟通复杂性等于花园软管的复杂性； （3）我们在这些无内存的通信模型之间表现出各种指数分离。 我们以一个有趣的开放问题结尾：我们能找到一个显式函数f和通用常数c> 1，而无内存通信复杂性至少为$ c \ log n $？请注意，$ c \ geq 2+ \ varepsilon $将暗示$ω（n^{2+ \ varepsilon}）$对于一般公式大小的下限，在1966年由Nečiporuk的最佳下限上改善了下限。
We study the communication complexity of computing functions $F:\{0,1\}^n\times \{0,1\}^n \rightarrow \{0,1\}$ in the memoryless communication model. Here, Alice is given $x\in \{0,1\}^n$, Bob is given $y\in \{0,1\}^n$ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x; the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study space-bounded communication models. We establish the following: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose complexity; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c>1 for which the memoryless communication complexity is at least $c \log n$? Note that $c\geq 2+\varepsilon$ would imply a $Ω(n^{2+\varepsilon})$ lower bound for general formula size, improving upon the best lower bound by Nečiporuk in 1966.
