More on Covers

Eyal Kushilevitz, Noam NisanCambridge 1996 · DOI · OpenAlex

Abstract

In Chapter 1 we saw that every communication protocol induces a partition of the space of possible inputs into monochromatic rectangles and learned of two lower bound techniques for the number of rectangles in such a partition. In this section we study how closely these combinatorial measures relate to communication complexity and to each other.
BibTeX
@inproceedings{kushilevitz1996more,
  author = {Eyal Kushilevitz and Noam Nisan},
  title = {{More on Covers}},
  booktitle = {Cambridge},
  year = {1996},
  doi = {10.1017/cbo9780511574948.003},
}

Loading related content...

Figure