ACM Transactions on

Computation Theory (TOCT)

Latest Articles

A Universal Tree Balancing Theorem

We present a general framework for balancing expressions (terms) in the form of so-called tree straight-line programs. The latter can be seen as circuits over the free term algebra extended by contexts (terms with a hole) and the operations, which insert terms/contexts into contexts. In Ref. [16], it was shown that one can compute for a given term... (more)

Reconstruction of Full Rank Algebraic Branching Programs

An algebraic branching program (ABP) A can be modelled as a product expression X1amp;middot; X2… Xd, where X1 and Xd are 1 × w and w... (more)

Surjective H-Colouring over Reflexive Digraphs

The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, the property of a structure that all of its endomorphisms that do not have range of size 1 are... (more)

The Complexity of Boolean Surjective General-Valued CSPs

Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a (Q ∪ {∞ })-valued objective function... (more)

Read-Once Branching Programs for Tree Evaluation Problems

Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman, and Santhanam introduced the Tree Evaluation Problem (TEP). For fixed... (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

Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

Distribution Testing Lower Bounds via Reductions from Communication Complexity

Characterization and Lower Bounds for Branching Program Size using Projective Dimension

All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name