Latest Articles

## Constant-Error Pseudorandomness Proofs from Hardness Require Majority

Research in the 1980s and 1990s showed how to construct a pseudorandom generator from a function that is hard to compute on more than 99% of the... (more)

## On Minrank and Forbidden Subgraphs

The minrank over a field F of a graph G on the vertex set { 1,2,… ,n} is the minimum possible rank of a matrix M ∈ Fn × n such that Mi, i ≠ 0 for every i, and Mi, j =0 for every distinct non-adjacent vertices i and j in G. For an integer n, a graph H, and a field F, let g(n,H, F) denote the maximum possible... (more)

## Bounded Independence versus Symmetric Tests

For a test T ⊆ {0, 1}n, define k*(T) to be the maximum k such that there exists a k-wise uniform distribution over {0, 1}n whose support is a subset of T. For Ht = {x ∈ {0, 1}n : | ∑ixi − n/2| ≤ t}, we prove k*(Ht) = Θ (t2/n + 1). For Sm, c... (more)

## Representations of Monotone Boolean Functions by Linear Programs

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of computation for partial Boolean functions. Using this... (more)

## Approximating Pairwise Correlations in the Ising Model

In the Ising model, we consider the problem of estimating the covariance of the spins at two specified vertices. In the ferromagnetic case, it is easy... (more)

## Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

A function f:{ −1,1}n → { −1,1} is a k-junta if it depends on at most k of its variables. We consider the... (more)

## PPSZ for k ≥ 5: More Is Better

We show that for k ≥ 5, the PPSZ algorithm for k-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every k≥ 5, there is a strictly increasing function f: [0,1] → R with f(0) = 0 that has the following property. If F is a k-CNF formula over n variables and |sat(F)|... (more)

## New Resolution-Based QBF Calculi and Their Proof Complexity

Modern QBF solvers typically use two different paradigms, conflict-driven clause learning (CDCL) solving or expansion solving. Proof systems for... (more)

## New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deal with time-bounded Kolmogorov complexity are prominent candidates for... (more)

## Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

This article analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems without changing... (more)

### Editor-in-Chief Call for Nominations

The term of the current Editor-in-Chief (EiC) of the ACM Transactions on Computation Theory (ToCT) is coming to an end, and the ACM Publications Board has set up a nominating committee to assist the Board in selecting the next EiC.

Nominations, including self-nominations, are invited for a three-year term as ToCT EiC, beginning on January 1, 2020. The EiC appointment may be renewed at most one time. This is an entirely voluntary position, but ACM will provide appropriate administrative support.

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

##### Forthcoming Articles
Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:
1. There exists an explicit n-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) such that every ROABP computing it requires 2^{\Omega(n)} size.

2. Any multilinear depth three circuit computing IMM_{n,d} (the iterated matrix multiplication polynomial formed by multiplying d, n \times n symbolic matrices) has n^{\Omega(d)} size. IMM_{n,d} can be easily computed by a poly(n,d) sized ROABP.

3. Further, the proof of 2 yields an exponential separation between multilinear depth four and multilinear depth three circuits: There is an explicit n-variate, degree d polynomial computable by a poly(n) sized multilinear depth four circuit such that any multilinear depth three circuit computing it has size n^{\Omega(d)}. This improves upon the quasi-polynomial separation of [Raz and Yehudayoff 2009] between these two models.

The hard polynomial in 1 is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure [Raz 2006; 2009; Forbes and Shpilka 2013], while 2 is proved via a new adaptation of the dimension of the partial derivatives measure of [Nisan and Wigderson 1996]. Our lower bounds hold over any field.

#### Search versus Decision for Election Manipulation Problems

###### All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name