Time, space, and randomness: Trade-offs in various models

Parallel time and space are perhaps the two most fundamental resources in computation. They appear to be orthogonal, as reducing one potentially increases the other. The relation between them is a fascinating question. Interestingly, some duality phenomena between them have been observed that seem to suggest the existence of a nontrivial law behind it. Randomness is another resource. There are several important problems for which the most efficient algorithms known are randomized. However, randomized algorithms typically depend on the availability of a perfect random source, whose existence even in nature is debatable. So if possible, we’d like to convert randomized algorithms into deterministic ones. To find general relations among parallel time, space, and randomness is a very challenging task, and very little is known. We will study this issue in the setting of restricted complexity classes, hoping to get some concrete results and to gain some intuition towards the more general situation. In Chapter 2, we use monotone planar circuits to explore some duality phenomena between space (circuit width) and parallel time (circuit depth). We show that standard classes such as AC0 and PH defined by constant depth circuits can also be defined by constant width monotone planar circuits. We also show that any stratified monotone planar circuit (one with all inputs in the same face) of polynomial size can be collapsed into an equivalent one of poly-logarithmic depth or width. In Chapter 3, we study constant depth circuits in greater detail. We show that for constant k, the reachability problem (usually used to capture space-bounded classes) on width k grid graphs is complete for the kth level of the AC 0 hierarchy, while the succinct version of this problem is complete for the kth level of the PH hierarchy. In Chapter 4, we consider randomness in space-bounded computation. The best known pseudorandom generator that fools all randomized logspace algorithms needs a seed of O(log2 n) random bits, and the hope is to reduce this number to O(log n). We study an important special case of this problem and construct pseudorandom generators that use O(log3/2 n) bits to fool combinatorial rectangles. In Chapter 5, we study the deterministic DNF approximate counting problem, an important step towards the derandomization of randomized parallel computations. During the process, we solve a minmax integer programming problem, which turns out to have applications to other problems like routing to minimize congestion and dimensions of partially ordered sets