Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 8 Issue 2, May 2016

Testing Read-Once Formula Satisfaction
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish
Article No.: 5
DOI: 10.1145/2897184

We study the query complexity of testing for properties defined by read-once formulas, as instances of massively parametrized properties, and prove several testability and nontestability results. First, we prove the testability of any...

Tractable Parameterizations for the Minimum Linear Arrangement Problem
Michael R. Fellows, Danny Hermelin, Frances Rosamond, Hadas Shachnai
Article No.: 6
DOI: 10.1145/2898352

The Minimum Linear Arrangement (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable...

On Sample-Based Testers
Oded Goldreich, Dana Ron
Article No.: 7
DOI: 10.1145/2898355

The standard definition of property testing endows the tester with the ability to make arbitrary queries to “elements” of the tested object. In contrast, sample-based testers only obtain independently distributed elements (a.k.a....