ACM DL

Computation Theory (TOCT)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computation Theory (TOCT), Volume 3 Issue 1, August 2011

Kolmogorov Complexity in Randomness Extraction
John M. Hitchcock, A. Pavan, N. V. Vinodchandran
Article No.: 1
DOI: 10.1145/2003685.2003686

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity extractor, thus establishing a fundamental...

On the Power of Isolation in Planar Graphs
Raghav Kulkarni
Article No.: 2
DOI: 10.1145/2003685.2003687

We study (deterministic) isolation for certain structures in directed and undirected planar graphs. The motivation for undertaking such a study comes from recent positive results on this topic. For example: Bourke et al. [2009] isolate a directed...

Approximate Query Complexity
Clifford Smyth
Article No.: 3
DOI: 10.1145/2003685.2003688

Let f : {0, 1}n → {0, 1}. Let μ be a product probability measure on {0, 1}n. For ε ≥ 0, we define (f), the ε-approximate decision tree complexity of f, to...