ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

Distribution Testing Lower Bounds via Reductions from Communication Complexity

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the... (more)

Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy

We introduce an idea called anti-gadgets for reductions in complexity theory. These anti-gadgets are presented as graph fragments, but their effect is... (more)

Characterization and Lower Bounds for Branching Program Size using Projective Dimension

We study projective dimension, a graph parameter, denoted by pd(G) for a bipartite graph G, introduced by Pudlák and Rödl (1992). For... (more)

Multi-Party Protocols, Information Complexity and Privacy

We introduce a new information-theoretic measure, which we call Public Information Complexity (PIC), as a tool for the study of multi-party... (more)

Communication Complexity and Graph Families

Given a graph G and a pair (F1, F2) of graph families, the function GDISJG,F1,F2 takes as input, two induced subgraphs G1 and G2 of G, such that G1 ∈ F1 and G2 ∈ F2 and returns 1 if V(G1)∩ V(G2)=∅ and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs... (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

Monotone Properties of k-Uniform Hypergraphs are Weakly Evasive

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].

Strong Locally Testable Codes with Relaxed Local Decoders

On The Entropy Loss and Gap of Condensers

Tight lower bounds for the complexity of multicoloring

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

Corrigendum to Affine Relativization: Unifying the Algebrization and Relativization Barriers

Split Contraction: The Untold Story

All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name