ACM Transactions on

Computation Theory (TOCT)

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)


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

Reconstruction of full rank algebraic branching programs

The complexity of Boolean surjective general-valued CSPs

A universal tree balancing theorem

Streaming Communication Protocols

Surjective H-Colouring over Reflexive Digraphs

Read-Once Branching Programs for Tree Evaluation Problems

All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name