Ph.D Thesis

Ph.D StudentVolkovich Ilya
SubjectPolynomial Identity Testing and its Relation to some
Algebraic Problems
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Amir Shpilka
Full Thesis textFull thesis text - English Version


In this thesis we study the fundamental problem of Polynomial Identity Testing (PIT). The problem is one of a few natural problems that have an efficient randomized algorithm (coRP) but lack deterministic ones. We present several deterministic algorithms for several important instances of PIT. In addition, we show connections between PIT and other problems sharing this virtue. In particular, we show that PIT is essentially equivalent to some restricted version of the polynomial factorization problem; and present a generic scheme that can be used to strengthen efficient PIT algorithms to yield efficient algorithms for testing whether a given polynomial can be computed by an arithmetic circuit of a specific form.