ACM Transactions on

Computation Theory (TOCT)

Latest Articles

Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization

We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds, formally referred to as... (more)

Tight Lower Bounds for the Complexity of Multicoloring

In the multicoloring problem, also known as (a:b)-coloring or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign... (more)

On the Entropy Loss and Gap of Condensers

Many algorithms are proven to work under the assumption that they have access to a source of random, uniformly distributed bits. However, in practice, sources of randomness are often imperfect, giving n random bits that have only k < n min-entropy. The value n−k is called the entropy gap of the source. Randomness condensers are hash... (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

Monotone Properties of k-Uniform Hypergraphs are Weakly Evasive

Strong Locally Testable Codes with Relaxed Local Decoders

On Minrank and Forbidden Subgraphs

Constant-error pseudorandomness proofs from hardness require majority

Corrigendum to Affine Relativization: Unifying the Algebrization and Relativization Barriers

Split Contraction: The Untold Story

All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name