ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

Circuits and Expressions over Finite Semirings

The computational complexity of the circuit and expression evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or a multiplicative identity. The following dichotomy is shown: If a finite semiring is such that (i) the multiplicative semigroup is solvable and (ii) it does not contain a... (more)

Property Testing of Joint Distributions using Conditional Samples

In this article, we consider the problem of testing properties of joint distributions under the Conditional Sampling framework. In the standard... (more)

Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin systems in certain parameter regimes.... (more)

Simultaneous Feedback Vertex Set: A Parameterized Perspective

For a family F of graphs, a graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. For an integer α ≥ 1, an n-vertex (multi) graph G... (more)

NEWS

About TOCT

The ACM Transactions on Computation Theory (TOCT) is a peer-reviewed journal that explores the mathematical nature of computation and it's theoretical limitations (with an emphasis on computational complexity, foundations of cryptography and other computation-based topics in theoretical computer science).

read more
Forthcoming Articles

A universal tree balancing theorem

Streaming Communication Protocols

All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name