Paper Info
Title
An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game
Abstract
We give an $5\cdot n^{\log_{30}5}$ upper bund on the complexity of the communication game introduced by G. Gilmer, M. Kouck\'y and M. Saks \cite{saks} to study the Sensitivity Conjecture \cite{linial}, improving on their $\sqrt{999\over 1000}\sqrt{n}$ bound. We also determine the exact complexity of the game up to $n\le 9$.
Year
Venue
Field
2015
Electronic Colloquium on Computational Complexity
Discrete mathematics,Combinatorics,Upper and lower bounds,Conjecture,Mathematics
DocType
Volume
Citations 
Journal
abs/1506.06456
2
PageRank 
References 
Authors
0.36
4
1
Name
Order
Citations
PageRank
Mario Szegedy13358325.80