On some computational problems in randomization, interaction and inapproximability.

摘要

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.