Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 1 Issue 2, September 2009

Improved Separations between Nondeterministic and Randomized Multiparty Communication
Matei David, Toniann Pitassi, Emanuele Viola
Article No.: 5
DOI: 10.1145/1595391.1595392

We exhibit an explicit function f : {0, 1}n →{0, 1} that can be computed by a nondeterministic number-on-forehead protocol communicating O(logn) bits, but that requires nΩ(1) bits of...

Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers
Venkatesan Guruswami, Prasad Raghavendra
Article No.: 6
DOI: 10.1145/1595391.1595393

A classic result due to Håstad established that for every constant ϵ > 0, given an overdetermined system of linear equations over a finite field Fq where each equation depends on exactly 3 variables...

Sound 3-Query PCPPs Are Long
Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah
Article No.: 7
DOI: 10.1145/1595391.1595394

We initiate the study of the trade-off between the length of a probabilistically checkable proof of proximity (PCPP) and the maximal soundness that can be guaranteed by a 3-query verifier with oracle access to the proof. Our main observation is...