Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 3 Issue 2, January 2012

Pebbles and Branching Programs for Tree Evaluation
Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
Article No.: 4
DOI: 10.1145/2077336.2077337

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
DOI: 10.1145/2077336.2077338

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
DOI: 10.1145/2077336.2077339

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...