ACM Transactions on

Computation Theory (TOCT)

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)


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

Representations of Monotone Boolean Functions by Linear Programs

Approximating Pairwise Correlations in the Ising Model

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

All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name