TY  - BOOK
AU  - Partha Mukhopadhyay
TI  - On Polynomial Identity Testing and Related Problems
PY  - 2009///
KW  - Computer Science
KW  - Identity Testing
N1  - 2009
N2  - 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
UR  - http://www.imsc.res.in/xmlui/handle/123456789/129
ER  -