Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT) - Special issue on innovations in theoretical computer science 2012, Volume 5 Issue 3, August 2013

Introduction to the special issue on innovations in theoretical computer science 2012
Eric Allender, Shafi Goldwasser
Article No.: 8
DOI: 10.1145/2493252.2493253

Compressed matrix multiplication
Rasmus Pagh
Article No.: 9
DOI: 10.1145/2493252.2493254

We present a simple algorithm that approximates the product of n-by-n real matrices A and B. Let ‖AB‖F denote the Frobenius norm of AB, and b be a parameter determining the...

Linear-time decoding of regular expander codes
Michael Viderman
Article No.: 10
DOI: 10.1145/2493252.2493255

Sipser and Spielman (IEEE IT, [1996]) showed that any c,d)-regular expander code with expansion parameter >¾ is decodable in linear time from a constant fraction of errors. Feldman et al. (IEEE IT, [2007]) proved that...

Quantum rejection sampling
Maris Ozols, Martin Roetteler, Jérémie Roland
Article No.: 11
DOI: 10.1145/2493252.2493256

Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann [1951] and has many applications in classical computing. We...

High-confidence predictions under adversarial uncertainty
Andrew Drucker
Article No.: 12
DOI: 10.1145/2493252.2493257

We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of...