On Polynomial Identity Testing and Related Problems[HBNI Th12]

Abstract

The polynomial identity Testing problem and its connection to several other important complexity theoretic problems are studied in this thesis. Polynomial identity testing problem is considered over commutative and non commutative models of computation. Efficient randomized identity testing algorithm over finite rings is obtained. Connections established between ideal membership problem and identity testing as a by product new understanding of identity testing is obtained for depth-3 circuits. Over non commutative model, new efficient deterministic identity testing and polynomial interpolation algorithms for small degree and sparse polynomials are given. Derandomization consequences of the isolation lemma in the context of circuit size lower bounds are obtained with relation to identity testing. Also a query efficient quantum algorithm is obtained for testing 'if a given polynomial is an identity(ie., zero at all the points)' for a given ring.