Ph.D Thesis

Ph.D StudentKarnin Zohar
SubjectDerandomization of Algebraic and Geometric Problems in
Theoretical Computer Science
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Amir Shpilka
Full Thesis textFull thesis text - English Version


This thesis deals with the question of whether randomized computations are more efficient than their deterministic counterparts. One of the most fundamental problems in theoretical computer science is to establish which problems are solvable via efficient algorithms. The most famous question regarding this problem is whether P is equal to NP. Stated informally, does non-determinism help? An additional major question in the area of computational complexity is whether randomness helps. Formally stated, does P equal BPP? In this case, the common conjecture is that P=BPP. A strong reasoning for this conjecture is by Nisan and Wigderson, that showed that sufficiently strong circuit lower bounds would imply P=BPP.

The motivation for derandomization extends beyond the area of computational complexity. A randomized algorithm is assumed to have access to truly random bits, independent of each other. It is unclear whether the physical world has sources of perfect randomness. It could be the case that an algorithm that is proven to work given truly random bits will fail given a sequence of bits that seems random but in fact has some hidden correlation or bias.

Probabilistic constructions of combinatorial objects often do not provide efficient algorithms for using them. A randomly constructed object often requires a large amount of space for its description, at times exponential in the parameters. Thus, a motivation exists for a deterministic construction of such objects. Finding such explicit constructions often demonstrate a better understanding of the underlying problem and in many cases lead to better uses of the object. In addition to all immediate motivations, the research of derandomization has had many unexpected applications in the following areas: Data structures, distributed computing, circuit lower bounds, error correcting codes, memory saving in streaming algorithms, and more.

The derandomization problems on which we have worked can be divided into two categories. The first involves arithmetic circuits, a common computational model for computing multivariate polynomials. The second category involves geometrical objects which are related to many algorithmic questions in theoretical computer science.