<p>In the book <em>Communication Complexity</em> by Eyal Kushilevitz and Noam Nisan, there is a proof that</p>
<p><span class="math-container">$$
D(f) = O(N^0(f) \cdot N^1(f)),
$$</span></p>
<p>where:</p>
<ol>
<li><span class="math-container">$D(f)$</span> is the deterministic communication complexity of <span class="math-container">$f$</span>,</li>
<li><span class="math-container">$N^0(f)$</span> and <span class="math-container">$N^1(f)$</span> are the non-deterministic communication complexities of <span class="math-container">$f$</span> for outputs 0 and 1, respectively.</li>
</ol>
<p>I would like to know what is the constant hidden in the <span class="math-container">$O$</span>-notation of this proof? Is this constant greater than 1? This is relevant to determine whether the following inequality holds:
<span class="math-container">$$
D(f) \leq (N(f))^2,
$$</span></p>
<p>Is there another way to bound <span class="math-container">$D(f)$</span> in terms of <span class="math-container">$N(f)$</span> without involving a constant factor?</p>
<p>Any clarification or additional insight would be greatly appreciated!</p>

CC BY-SA 4.0
2024-12-05T14:16:13.317Z
See Theorem 13.3.2 here: https://lovasz.web.elte.hu/kurzusok/complexity.pdf for the cited theorem and a bit better upper bound right after.
domotorp
CC BY-SA 4.0
2024-12-07T08:43:31.327Z
@domororp That looks like an answer.
Emil Jeřábek
<communication-complexity>
What is the constant in the proof of $D(f) = O(N^0(f) \cdot N^1(f))$
OriFrid
# What is the constant in the proof of $D(f) = O(N^0(f) \cdot N^1(f))$

(Asked by: username_0 on 2024-12-05)

In the book *Communication Complexity* by Eyal Kushilevitz and Noam Nisan, there is a proof that

$$
D(f) = O(N^0(f) \cdot N^1(f)),
$$

where:

1. $D(f)$ is the deterministic communication complexity of $f$,
2. $N^0(f)$ and $N^1(f)$ are the non-deterministic communication complexities of $f$ for outputs 0 and 1, respectively.

I would like to know what is the constant hidden in the $O$-notation of this proof? Is this constant greater than 1? This is relevant to determine whether the following inequality holds:
$$
D(f) \leq (N(f))^2,
$$

Is there another way to bound $D(f)$ in terms of $N(f)$ without involving a constant factor?

Any clarification or additional insight would be greatly appreciated!

**Tags:** communication-complexity
> **Comments:**
> **username_1**: See Theorem 13.3.2 here: https://lovasz.web.elte.hu/kurzusok/complexity.pdf for the cited theorem and a bit better upper bound right after.  
> **username_2**: @domororp That looks like an answer.  

---

## 0 answers

