| This thesis consists of three components. In the first component, we study the power of randomness in the context of space bounded computations. A classical question here is whether every randomized algorithm can be simulated deterministically without much loss of efficiency in terms of space/time usage. Our work extends the following two breakthrough results on the topic. Firstly, Nisan showed that any randomized algorithm A can be simulated deterministically with only a quadratic blow-up in space usage. The running time of his simulation is polynomial in that of A. Secondly, Saks and Zhou designed a simulation that requires only sub-quadratic amount of space, but needs time super-polynomial (in the running time of A). We generalize these results by designing a sequence of simulations with varying time-space requirements. The above two simulations lie at the two extremes of the sequence. The rest of the sequence smoothly interpolates the two simulations in terms of time-space usage.; The second part of the thesis deals with the symmetric alternation class ( Sp2 ). In an important result about Sp2 , Cai showed that Sp2 ⊆ ZPPNP. The reverse containment remains open. Our first result is that zero-error algorithms making only one query to the NP oracle can be simulated in Sp2 . We next prove a lowness result for Sp2 : every self-reducible language having polynomial size circuits is low for Sp2 . Using this result, we improve some known Karp-Lipton type collapse results.; In the last part, we prove some inapproximability results. First, we consider a special case of the classical traveling salesman problem (TSP) where the distances are either one or two. Papadimitriou and Yannakakis showed that the problem is MAXSNP-Hard even the underlying graph has a degree bound of four. We show that the problem is MAXSNP-Hard even over 3-regular graphs, and over line graphs. The latter problem is closely related to a certain pebble game that has applications in database systems. Secondly, we show that the weighted context sensitive string matching problem is MAXSNP-Hard and cannot be approximated within a factor of 2278/2277. |
