What are the best polylogarithmic lower bounds known for $\Sigma_2$-communication complexity on an explicit function? Are there any known candidate functions for $O(n^\epsilon)$ communication complexity? The only results I am aware of are of the negative type, with Katz and independently Hambardzumyan, Hatami, and Ndiaye both finding a counterexample to Problem 4.9 in Jukna's Boolean Function Complexity, which would have implied polynomial $\Sigma_2$ communication bounds.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This paper by Lokam shows a lower bound of $3\log n$ on the $\Sigma_2$-communication complexity of inner product and related functions: https://www.semanticscholar.org/paper/Graph-Complexity-and-Slice-Functions-Lokam/fc82031341bd6284175b852f90d53557dd8311f7
The paper is phrased in terms of graph complexity, and therefore states the lower bound as $\log^3 n$, but this corresponds to $3\log n$ for communication complexity.
I am not aware of stronger lower bounds.
