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

Monotone Properties of k-Uniform Hypergraphs are Weakly Evasive

Communication Complexity of Pairs of Graph Families with Applications

Lower bounds for Sum and Sum of Products of Read-Once Formulas

We study limitations of polynomials computed by depth two circuits built over
read-once formulas (ROFs). In particular,
1) We prove a 2^{\Omega(n/\log n)} lower bound for the sum of ROFs computing the 2n-variate polynomial in VP defined by Raz and Yehudayoff ~[CC, 2008].

2) We obtain a 2^{Omega(sqrt{n})} lower bound on the size of \Sigma\Pi^{[n^{1/15}]} arithmetic circuits built over restricted ROFs of unbounded depth computing the permanent of an nxn matrix (superscripts on gates denote bound on the fan-in). The restriction is on the number of variables with + gates as a parent in a proper sub formula of the ROF to be bounded by \sqrt{n}. This proves an exponential lower bound for a subclass of possibly non-multilinear formulas of unbounded depth computing the permanent polynomial.
3) We also show an exponential lower bound for the above model against a polynomial in VP.
4) Finally we observe that the techniques developed yield an exponential lower bound on the size of \Sigma\Pi^{[N^{1/30}]} arithmetic circuits built over syntactically multi-linear \Sigma\Pi\Sigma^{[N^{1/4}]} arithmetic circuits computing a product of variable disjoint linear forms on N variables, where the superscripts on gates denote bound on the fan-in.

Our proof techniques are built on the measure developed by Kumar et. al.[2016, TOCT] and are based on a non-trivial analysis of ROFs under random partitions. Further, our results exhibit strengths and provide more insight into the lower bound techniques introduced by Raz~[STOC, 2004].

Tight lower bounds for the complexity of multicoloring

Multi-Party Protocols, Information Complexity and Privacy

Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization

All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name