<p>This paper by Lokam shows a lower bound of <span class="math-container">$3\log n$</span> on the <span class="math-container">$\Sigma_2$</span>-communication complexity of inner product and related functions:
<a href="https://www.semanticscholar.org/paper/Graph-Complexity-and-Slice-Functions-Lokam/fc82031341bd6284175b852f90d53557dd8311f7" rel="nofollow noreferrer">https://www.semanticscholar.org/paper/Graph-Complexity-and-Slice-Functions-Lokam/fc82031341bd6284175b852f90d53557dd8311f7</a></p>
<p>The paper is phrased in terms of graph complexity, and therefore states the lower bound as <span class="math-container">$\log^3 n$</span>, but this corresponds to <span class="math-container">$3\log n$</span> for communication complexity.</p>
<p>I am not aware of stronger lower bounds.</p>

CC BY-SA 4.0
2022-12-13T08:25:54.703Z
2022-12-13T08:25:54.703Z
Or Meir
<p>What are the best polylogarithmic lower bounds known for <span class="math-container">$\Sigma_2$</span>-communication complexity on an explicit function? Are there any known candidate functions for <span class="math-container">$O(n^\epsilon)$</span> 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 <em>Boolean Function Complexity</em>, which would have implied polynomial <span class="math-container">$\Sigma_2$</span> communication bounds.</p>

<communication-complexity><polynomial-hierarchy>
What are the up-to-date results on explicit lower bounds for $\Sigma_2$ communication complexity?
Stefan G.
# What are the up-to-date results on explicit lower bounds for $\Sigma_2$ communication complexity?

(Asked by: username_0 on 2022-12-13)

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.

**Tags:** communication-complexity, polynomial-hierarchy


---

## 1 answers

### Answer by username_1 on 2022-12-13. Score: 4

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.


---

