New results on Noncommutative and Commutative Polynomial Identity Testing

Simple item page
dc.creatorArvind, V.
dc.creatorMukhopadhyay, Partha
dc.creatorSrinivasan, Srikanth
dc.date2008-01-03
dc.date.accessioned2026-07-07T08:52:19Z
dc.date.available2026-07-07T08:52:19Z
dc.descriptionUsing ideas from automata theory we design a new efficient (deterministic) identity test for the \emph{noncommutative} polynomial identity testing problem (first introduced and studied in \cite{RS05,BW05}). We also apply this idea to the reconstruction of black-box noncommuting algebraic branching programs. Assuming the black-box model allows us to query the ABP for the output at any given gate, we can reconstruct an (equivalent) ABP in deterministic polynomial time. Finally, we explore commutative identity testing when the coefficients of the input polynomial come from an arbitrary finite commutative ring with unity.
dc.description23 pages, no figure
dc.identifierhttps://arxiv.org/abs/0801.0514
dc.identifierhttp://arxiv.org/abs/0801.0514
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/145242
dc.subjectComputational Complexity
dc.titleNew results on Noncommutative and Commutative Polynomial Identity Testing
dc.typetext

Files

Collections

arXiv