1
$\begingroup$

I have been wracking my head around the understanding on how to calculate $N_{1}(f)$ and $N_{0}(f)$ from the communication matrix.

Definitions:
$N_{1}(f)$ = least cost of non-deterministic protocol that accepts $f^{-1}(1) = \{(x,y) : f(x,y) = 1 \}$

$N_{1}(f)$ = ceiling( log(number of monochromatic rectangles needed to cover $f^{-1}(1)$))

Examples:
I would like to connect understand how this gets translated into the following two examples:

Equality
We know that the communication matrix has 1s on the diagonal and everything else is covered with 0.
$N_{1}(f) = n$ - this makes sense, I need exactly $n$ rectangles to cover my 1s on the diagonal, one rectangle per cell.
$N_{0}(f) = \log n + 1$ - this does not make sense. How can you cover all 0s with only that many monochromatic rectangles?

Greater Than
We know that the communication matrix has 1s on the diagonal and on top of it and everything else is covered with 0s.
$N_{1}(f) = n$ - I am assuming the rectangles are now not just an individual cell in the diagonal, but the whole row.
$N_{0}(f) = n$ - I am assuming the rectangles are now the entire column.

If my understanding for $N_{0}(f)$ for the Greater Than is correct, then I do not understand how the colouring works for the Equality problem.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Here are the $\log n + 1$ rectanges that cover all 0s in the case of the Equality function: for all $i \in [\log n]$ and $b \in \{0, 1\}$, there is a rectangle $$ \{ (x,y) : x_i = b, y_i \neq b \} = \{ x : x_i = b \} \times \{y : y_i \neq b \} . $$

Improve this answer
$\endgroup$
10
  • $\begingroup$ But the number of such rectangles is still greater than than the rectangles on diagonal... It is impossible to colour all 0s in less than n-1 where n is the number of entries on each axis. $\endgroup$
    – Meki21
    Commented Dec 16, 2023 at 18:59
  • $\begingroup$ There are $n$ rectangles on the diagonal, an exponentially larger number. $\endgroup$
    – Yuval Filmus
    Commented Dec 16, 2023 at 19:23
  • $\begingroup$ I agree. The way I colour my 0s is the following. For each row I can put all 0s left and all 0s right of the diagonal (the only cell that contains 1 in that given row) in one rectangle. Which means, in total I will have 2*(n-1) + 2 rectangles $\endgroup$
    – Meki21
    Commented Dec 16, 2023 at 19:27
  • $\begingroup$ For the sake of nondeterministic complexity we need a cover, not a partition. $\endgroup$
    – Yuval Filmus
    Commented Dec 16, 2023 at 19:59
  • 1
    $\begingroup$ A deterministic protocol is a partition of the communication matrix into monochromatic rectangles. (This is perhaps where you got the idea of coloring.) A non-deterministic protocol is a covering of the 1-s of the communication matrix by 1-monochromatic rectangles. The covering need not be a partition. If a point is covered by $k$ rectangles, this means that it has $k$ witness, which is ok as long as $k \ge 1$. $\endgroup$
    – Yuval Filmus
    Commented Dec 17, 2023 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.