enter search term and/or author name
We introduce the tree evaluation problem, show that it is in LogDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem...
Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
Anna Gal, Andrew Mills
Article No.: 5
Locally decodable codes are error-correcting codes with the extra property that, in order to retrieve the value of a single input position, it is sufficient to read a small number of positions of the codeword. We refer to the probability of...
The Value of Multiple Read/Write Streams for Approximating Frequency Moments
Paul Beame, Trinh Huynh
Article No.: 6
We consider the read/write streams model, an extension of the standard data stream model in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most...