Gilad Tsur

Abstract of Master Thesis (Weizmann Inst., 2007)

Polylogarithmic Time and Query Complexity

One of the major challenges in the modern design of algorithms is dealing with huge data sets. In some application domains it is desirable to have algorithms that run in time that is not even linear in the size of the input. In this thesis we introduce and study complexity classes that refer to computations that access only a polylogarithmic number of bits of their input. We study two types of complexity classes - those induced by a polylogarithmic limit on the computation time, and those induced by a limit on the number of bits that may be queried during the computation, with no time restriction. We show that in both cases deterministic and randomized computations cannot, in general, decide all the sets that are decidable using nondeterminism. In contrast, in the query-bounded case, we show that sets decidable both nondeterministically and co-nondeterministically are deterministically decidable. While the separation results are relatively easy, the technical crux of the thesis is giving a deterministic algorithm for sets in the intersection of polylogarithmic nondeterministic and co-nondeterministic classes. Following our study of polylogarithmic time and query decision problems, we investigate promise problems that can be solved in polylogarithmic-time. We claim that the promise problem setting is more natural for polylogarithmic-time computations, and is, in fact, the setting where such computations are generally studied. We conclude our study by investigating two variations of polylogarithmic-time hierarchies - the polylogarithmic-time analogues of PH.

NOTE: After submitting the thesis, it was discovered that many of our results, mostly regarding query complexity, were known. See details in the (revised) introduction.

Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, January 2007.

Available: the thesis (in PDF file).

Back to Oded Goldreich's homepage.