On Polynomial Identity Testing and Related Problems[HBNI Th 12]

DSpace/Manakin Repository

On Polynomial Identity Testing and Related Problems[HBNI Th 12]

Show full item record

Title: On Polynomial Identity Testing and Related Problems[HBNI Th 12]
Author: Partha Mukhopadhyay
Advisor: Arvind, V.
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2009
Pages: x; 110p.
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.
URI: http://hdl.handle.net/123456789/129

Files in this item

Files Size Format View
partham.pdf 815.4Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Search DSpace


Advanced Search

Browse

My Account