ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

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)

NEWS

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

Constant-error pseudorandomness proofs from hardness require majority

Bounded Independence versus Symmetric Tests

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

Split Contraction: The Untold Story

All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name