ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 522536, 9787302245179
Tsinghua University Press
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 readonly tape containing 2O(s) uniform random bits, and a usual error regime: onesided or twosided, 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 (oneway access) and the error is onesided 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 twosided 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 fanin) 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:

Copyright 20102011, Institute for Computer Science, Tsinghua University, All Rights Reserved.