ACM Transactions on Computation Theory

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 inputs. A more recent line of works showed, however, that if the generator has small error, then the proof ...

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 ∈ F^{n × n} such that M_{i, i} ≠ 0 for every i, and M_{i, j} =0 for every distinct non-adjacent vertices i and j in G. For an integer n, a graph H, ...

For a test T ⊆ {0, 1}ⁿ, define k^*(T) to be the maximum k such that there exists a k-wise uniform distribution over {0, 1}ⁿ whose support is a subset of T.

For H_t = {x ∈ {0, 1}ⁿ : | ∑_ix_i − n/2| ≤ t}, we prove k^*(H_t) = Θ (t²/n + 1).

For S_{m, c} = {x ∈ {0, 1}...

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of computation for partial Boolean functions. Using this model, we prove the following results.¹

(1) MLP circuits are superpolynomially stronger than monotone ...

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 to obtain an additive approximation to this covariance by repeatedly sampling from the relevant Gibbs ...

A function f:{ −1,1}ⁿ → { −1,1} is a k-junta if it depends on at most k of its variables. We consider the problem of tolerant testing of k-juntas, where the testing algorithm must accept any function that is ε-close to some k-junta and reject any ...

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

Modern QBF solvers typically use two different paradigms, conflict-driven clause learning (CDCL) solving or expansion solving. Proof systems for quantified Boolean formulas (QBFs) provide a theoretical underpinning for the performance of these solvers, ...

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deal with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence ...

This article analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results ...