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

DSpace/Manakin Repository

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

Show simple item record

dc.contributor.author Partha Mukhopadhyay
dc.date.accessioned 2009-10-01T06:02:50Z
dc.date.available 2009-10-01T06:02:50Z
dc.date.issued 2009-10-01T06:02:50Z
dc.date.submitted 2009
dc.identifier.uri http://hdl.handle.net/123456789/129
dc.description.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. en_US
dc.subject Identity Testing en_US
dc.title On Polynomial Identity Testing and Related Problems[HBNI Th 12] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Arvind, V.
dc.description.pages x; 110p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

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

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account