On the Power of Multiple Reads in a Chip

AbstractA chip algorithm is called r-multilective if it reads its input bits r times. In this paper we relate the r-bound communication complexity of a language L and the area requirement for an r-multilective chip algorithm of a related language L̃. More specifically A(L̃) ≥ C2r(L)/(2r − 1). Improving known lower bounds on the r-bound communication complexity of certain languages, we obtain several hierarchies of r-multilective languages depending on the parameter r. For example, if 0 < r < s, then there are constants 0 < c, c′ such that for infinitely many n there is a language Ln ⊆ {0, 1}n such that there is an s-multilective algorithm recognizing Ln using area at most c log n and any r-multilective algoerithm recognizing Ln requires area at least c′n/log n. Similar results have been known only for s = 2 and r = 1 and have been open in other cases