Ph.D Thesis | |
Ph.D Student | Volkovich Ilya |
---|---|
Subject | Polynomial Identity Testing and its Relation to some Algebraic Problems |
Department | Department of Computer Science | Supervisor | ASSOCIATE PROF. Amir Shpilka |
Full Thesis text | ![]() |
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.