Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 4 Issue 1, March 2012

Exact Quantum Algorithms for the Leader Election Problem
Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto
Article No.: 1
DOI: 10.1145/2141938.2141939

This article gives a separation between quantum and classical models in pure (i.e., noncryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of the leader...

Approximating Linear Threshold Predicates
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
Article No.: 2
DOI: 10.1145/2141938.2141940

We study constraint satisfaction problems on the domain {−1, 1}, where the given constraints are homogeneous linear threshold predicates, that is, predicates of the form sgn(w1x1 + ⋯ +...

Extractors and Lower Bounds for Locally Samplable Sources
Anindya De, Thomas Watson
Article No.: 3
DOI: 10.1145/2141938.2141941

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number d of the random input bits. As our main result, we construct a...