An O(n0.4732)O(n^{0.4732}) upper bound on the complexity of the GKS communication game

preprint2015arXivOpen access

Abstract

We give an 5⋅nlog⁡3055\cdot n^{\log_{30}5} upper bund on the complexity of the communication game introduced by G. Gilmer, M. Koucký and M. Saks \cite{saks} to study the Sensitivity Conjecture \cite{linial}, improving on their 9991000n\sqrt{999\over 1000}\sqrt{n} bound. We also determine the exact complexity of the game up to n≤9n\le 9.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.