论文标题
GKS沟通游戏上限的改进
An improvement of the upper bound for GKS communication game
论文作者
论文摘要
GKS游戏是由Justin Gilmer，Michal Koucky和Michael Saks在对敏感性猜想的研究中制定的。 Mario Szegedy发明了游戏协议，成本为$ O（N^{0.4732}）$。然后，使用两部分匹配的Devon Ingram获得了$ O（n^{0.4696}）$成本的协议。我们提出了Ingram方法的略有改进，并设计了一个协议，成本为$ O（N^{0.4693}）$。
The GKS game was formulated by Justin Gilmer, Michal Koucky, and Michael Saks in their research of the sensitivity conjecture. Mario Szegedy invented a protocol for the game with the cost of $O(n^{0.4732})$. Then a protocol with the cost of $O(n^{0.4696})$ was obtained by DeVon Ingram who used a bipartite matching. We propose a slight improvement of Ingram's method and design a protocol with cost of $O(n^{0.4693})$.
