On Polynomial Identity Testing and Related Problems
Material type:
TextPublication details: 2009Description: x; 110pSubject(s): Computer Science | Identity TestingOnline resources: Click here to access online Dissertation note: 2009Ph.DHBNI 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.
THESIS & DISSERTATION
| Current library | Home library | Call number | Materials specified | URL | Status | Date due | Barcode |
|---|---|---|---|---|---|---|---|
| IMSc Library | IMSc Library | HBNI Th-12 (Browse shelf (Opens below)) | Link to resource | Available | 62778 |
Browsing IMSc Library shelves Close shelf browser (Hides shelf browser)
2009
Ph.D
HBNI
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.
There are no comments on this title.