Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > OVERLAY:
Reports tagged with overlay:
TR13-189 | 21st December 2013
Periklis Papakonstantinou, Dominik Scheder, Hao Song

#### Overlays and Limited Memory Communication Mode(l)s

We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models.

We introduce the notion of rectangle overlay complexity of a function $f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>>

ISSN 1433-8092 | Imprint