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

## Friday, March 2, 2007

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment