Friday, March 2, 2007

Incorrect attribution for rank bound

In lecture on Wednesday, 2/28/2007, I asserted that the
communication complexity of a function f is lower bounded
by the log of the rank of the associated matrix M_f.
I then attributed this to Yao.

The attribution was incorrect. Nick Harvey pointed out
to me that the source of this lower bound is Mehlhorn
and Schmidt, STOC 1982. (Thanks to Nick for correcting
me.)

Nick also pointed out that my explanation of the
"tiling lower bound" was not clear (I agree). I
will try to post additional notes to clarify this.

Also I should have mentioned that the book "Communication
Complexity" by Kushilevitz and Nisan is an excellent place
to read more about the topic.

- Madhu

No comments: