<p>A natural problem where <span class="math-container">$D\approx N^0N^1$</span> was <a href="https://sci-hub.mksa.top/10.1109/focs.2015.70" rel="nofollow noreferrer">proved only recently</a> is the clique vs independent set problem: Given an <span class="math-container">$n$</span>-vertex graph, Alice gets a clique, while Bob gets an independent set, and their goal is to decide whether their sets are disjoint or intersect in a single vertex.</p>

CC BY-SA 4.0
2022-09-25T07:38:11.580Z
2022-09-25T07:38:11.580Z
domotorp
<p>I'm trying to lower bound the worst-case deterministic communication complexity of some special class of functions on <span class="math-container">$n$</span> variables, and I've shown that for every function <span class="math-container">$f$</span> in the class: <span class="math-container">$N^1(f) = O(\sqrt{n})$</span> and <span class="math-container">$N^0(f)=O(\sqrt{n})$</span>, where <span class="math-container">$N^1$</span> and <span class="math-container">$N^0$</span> are the nondeterministic and co-nondeterministic communication complexity of <span class="math-container">$f$</span>, respectively. I conjecture that the worst-case deterministic complexity <span class="math-container">$D(f) = \Omega(n)$</span>, which (from the general fact that <span class="math-container">$D(g) \le N^0(g)\cdot N^1(g)$</span>) is as high as possible given what I know so far.</p>
<p>My question is this: what are some natural functions <span class="math-container">$g$</span> such that <span class="math-container">$N^0(g) = O(\sqrt{n})$</span>, <span class="math-container">$N^1(g)=O(\sqrt{n})$</span>, and <span class="math-container">$D(g) = \Omega(n)$</span>? I am trying to reduce my problem to some such function <span class="math-container">$g$</span>, and if my conjecture is true, such a <span class="math-container">$g$</span> must have this value of <span class="math-container">$N^0$</span> and <span class="math-container">$N^1$</span>.</p>
<p>Kushilevitz and Nisan give one such example (4.13), which can be phrase like this: Alice and Bob both have <span class="math-container">$\sqrt{n}\times\sqrt{n}$</span> matrices, and <span class="math-container">$g$</span> outputs <span class="math-container">$1$</span> if and only if some row of both matrices are equal. This <span class="math-container">$g$</span> might suffice, but I haven't gotten the reduction right yet, and I'm having trouble finding any different examples to try. This property seems fairly natural, as it sort of &quot;splits the hardness&quot; perfectly evenly between verifying <span class="math-container">$0$</span> and verifying <span class="math-container">$1$</span>, so I'm wondering if any other natural example exist.</p>

<communication-complexity>
Natural hard communication problems with both nondeterministic and co-nondeterministic complexity of $\sqrt{n}$?
Clay Thomas
# Natural hard communication problems with both nondeterministic and co-nondeterministic complexity of $\sqrt{n}$?

(Asked by: username_0 on 2022-09-02)

I'm trying to lower bound the worst-case deterministic communication complexity of some special class of functions on $n$ variables, and I've shown that for every function $f$ in the class: $N^1(f) = O(\sqrt{n})$ and $N^0(f)=O(\sqrt{n})$, where $N^1$ and $N^0$ are the nondeterministic and co-nondeterministic communication complexity of $f$, respectively. I conjecture that the worst-case deterministic complexity $D(f) = \Omega(n)$, which (from the general fact that $D(g) \le N^0(g)\cdot N^1(g)$) is as high as possible given what I know so far.

My question is this: what are some natural functions $g$ such that $N^0(g) = O(\sqrt{n})$, $N^1(g)=O(\sqrt{n})$, and $D(g) = \Omega(n)$? I am trying to reduce my problem to some such function $g$, and if my conjecture is true, such a $g$ must have this value of $N^0$ and $N^1$.

Kushilevitz and Nisan give one such example (4.13), which can be phrase like this: Alice and Bob both have $\sqrt{n}\times\sqrt{n}$ matrices, and $g$ outputs $1$ if and only if some row of both matrices are equal. This $g$ might suffice, but I haven't gotten the reduction right yet, and I'm having trouble finding any different examples to try. This property seems fairly natural, as it sort of "splits the hardness" perfectly evenly between verifying $0$ and verifying $1$, so I'm wondering if any other natural example exist.

**Tags:** communication-complexity

---

## 1 answers

### Answer by username_1 on 2022-09-25. Score: 1 | Accepted answer

A natural problem where $D\approx N^0N^1$ was [proved only recently](https://sci-hub.mksa.top/10.1109/focs.2015.70) is the clique vs independent set problem: Given an $n$-vertex graph, Alice gets a clique, while Bob gets an independent set, and their goal is to decide whether their sets are disjoint or intersect in a single vertex.


---

