Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 8 Issue 1, February 2016

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
Stefan Kratsch, Dániel Marx, Magnus Wahlström
Article No.: 1
DOI: 10.1145/2858787

For a finite set Γ of Boolean relations, Max Ones SAT(Γ) and Exact Ones SAT(Γ) are generalized satisfiability problems where every constraint relation is from Γ, and the task is...

Characterizing Arithmetic Read-Once Formulae
Ilya Volkovich
Article No.: 2
DOI: 10.1145/2858783

An arithmetic Read-Once Formula (ROF for short) is a formula (i.e., a tree of computation) in which the operations are { +, ×} and such that every input variable labels at most one leaf. We give a simple characterization of...

Complexity Hierarchies beyond Elementary
Sylvain Schmitz
Article No.: 3
DOI: 10.1145/2858784

We introduce a hierarchy of fast-growing complexity classes and show its suitability for completeness statements of many nonelementary problems. This hierarchy allows the classification of many decision problems with a nonelementary complexity,...

An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model
Nir Ailon
Article No.: 4
DOI: 10.1145/2858785

Obtaining a nontrivial (superlinear) lower bound for computation of the Fourier transform in the linear circuit model has been a long-standing open problem for more than 40 years. An early result by Morgenstern from 1973, provides an...