**Latest Articles**
Emanuele Viola
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)

Ishay Haviv
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)

Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
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)

Mateus De Oliveira Oliveira, Pavel Pudlák
We introduce the notion of monotone linear programming circuits (MLP circuits), a model of computation for partial Boolean functions. Using this... (more)

Leslie Ann Goldberg, Mark Jerrum
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)

Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
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)

Dominik Scheder
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)

Olaf Beyersdorff, Leroy Chew, Mikoláš Janota
Modern QBF solvers typically use two different paradigms, conflict-driven clause learning (CDCL) solving or expansion solving. Proof systems for... (more)

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

Bart M. P. Jansen, Astrid Pieterse
This article analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems without changing... (more)

##### NEWS

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

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