Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 8 Issue 3, May 2016

Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices
Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma
Article No.: 8
DOI: 10.1145/2898437

We introduce the polynomial coefficient matrix and identify the maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against...

A Galois Connection for Weighted (Relational) Clones of Infinite Size
Peter Fulla, Stanislav Živný
Article No.: 9
DOI: 10.1145/2898438

A Galois connection between clones and relational clones on a fixed finite domain is one of the cornerstones of the so-called algebraic approach to the computational complexity of non-uniform Constraint Satisfaction Problems (CSPs). Cohen et al....

The List-Decoding Size of Fourier-Sparse Boolean Functions
Ishay Haviv, Oded Regev
Article No.: 10
DOI: 10.1145/2898439

A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most k nonzero Fourier coefficients. For a function f: F2n → R and parameters k and d, we prove...

Structural Properties of Nonautoreducible Sets
Dung Nguyen, Alan L. Selman
Article No.: 11
DOI: 10.1145/2898440

We investigate autoreducibility properties of complete sets for NEXP under different polynomial-time reductions. Specifically, we show under some polynomial-time reductions that there are complete sets for NEXP that are not autoreducible. We...

Counting Homomorphisms to Square-Free Graphs, Modulo 2
Andreas Göbel, Leslie Ann Goldberg, David Richerby
Article No.: 12
DOI: 10.1145/2898441

We study the problem ⊕HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph H. A characteristic feature of modular counting is that cancellations make wider...