Simulation Theorems via Pseudo-random Properties
Simulation Theorems via Pseudo-random Properties
复制标题
DOI：
10.1007/s00037-019-00190-7
复制
发表时间：
2017-04
影响因子：
1.4
通讯作者：
A. Chattopadhyay;M. Koucký;B. Loff;Sagnik Mukhopadhyay
中科院分区：
文献类型：
--
作者：
A. Chattopadhyay;M. Koucký;B. Loff;Sagnik Mukhopadhyay
我们将Raz & McKenzie （Combinatorica 19(3): 403-435, 1999）的确定性模拟定理推广到任何满足一定撞击性质的小管上。我们证明了内积和gap-Hamming满足这一性质，并由此得到了这些小工具的确定性模拟定理，其中小工具的输入大小是外函数输入大小的对数。这产生了第一个具有对数小工具大小的确定性模拟定理，回答了Göös， Pitassi和Watson提出的一个开放问题（在：第56届FOCS会议记录，2015）。我们的结果也暗示了之前索引小工具的结果，使用了比之前已知的更好的参数。此外，具有对数大小的小工具的模拟定理意味着确定性通信复杂性和1分区数的对数的二次分离，无论1分区数相对于输入大小有多高-这是Göös， Pitassi和Watson（2015）的先前结果无法实现的。
We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403–435, 1999), to any gadget which satisfies a certain hitting property. We prove that inner product and gap-Hamming satisfy this property, and as a corollary, we obtain a deterministic simulation theorem for these gadgets, where the gadget’s input size is logarithmic in the input size of the outer function. This yields the first deterministic simulation theorem with a logarithmic gadget size, answering an open question posed by Göös, Pitassi & Watson (in: Proceedings of the 56th FOCS, 2015).Our result also implies the previous results for the indexing gadget, with better parameters than was previously known. Moreover, a simulation theorem with logarithmic-sized gadget implies a quadratic separation in the deterministic communication complexity and the logarithm of the 1-partition number, no matter how high the 1-partition number is with respect to the input size—something which is not achievable by previous results of Göös, Pitassi & Watson (2015).