ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 522-536, 978-7-302-24517-9
Tsinghua University Press

Computationally Limited Randomness Authors : Matei David, Phuong Nguyen, Periklis Papakonstantinou, Anastasios Sidiropoulos [Download PDF]

Abstract:
The starting point of this work is the basic question of whether there exists a formal and meaningful way to limit the computational power that a time bounded randomized Turing Machine can employ on its randomness.
We attack this question using a fascinating connection between space and time bounded machines given by Cook [4]: a Turing Machine S running in space s with access to an unbounded stack is equivalent to a Turing Machine T running in time 2O(s). We extend S with access to a read-only tape containing 2O(s) uniform random bits, and a usual error regime: one-sided or two-sided, and bounded or unbounded. We study the effect of placing a bound p on the number of passes S is allowed on its random tape. It follows from Cook's results that:
•If p = 1 (one-way access) and the error is one-sided unbounded, S is equivalent to deterministic T .
• If p = ∞(unrestricted access), S is equivalent to randomized T (with the same error).
As our first two contributions, we completely resolve the case of unbounded error. We show that we cannot meaningfully interpolate between deterministic and randomized T by increasing p:
•If p = 1 and the error is two-sided unbounded, S is still equivalent to deterministic T .
•If p = 2 and the error is unbounded, S is already equivalent to randomized T (with the same error).
In the bounded error case, we consider a logarithmic space Stack Machine S that is allowed p passes over its randomness. Of particular interest is the case p = , where n is the input length, and i is a positive integer. Intuitively, we show that S performs polynomial time computation on its input and parallel (preprocessing plus NCi) computation on its randomness.
Formally, we introduce Randomness Compilers. In this model, a polynomial time Turing Machine gets an input x and outputs a (polynomial size, bounded fan-in) circuit Cx that takes random inputs. Acceptance of x is determined by the acceptance probability of Cx. We say that the randomness compiler has depth d if Cx has depth d(|x|). As our third contribution, we show that:
•S simulates, and is in turn simulated by, a randomness compiler with depth O((log n)i), and O((log n)i+1), respectively.
Randomness Compilers are a formal refinement of polynomial time randomized Turing Machines that might elicit independent interest.

Preview: