Header menu link for other important links
X
Identity testing, multilinearity testing, and monomials in read-once/twice formulas and branching programs
M. Mahajan, B.V.R. Rao,
Published in
2012
Volume: 7464 LNCS
   
Pages: 655 - 667
Abstract
We study the problem of testing if the polynomial computed by an arithmetic circuit is identically zero (ACIT). We give a deterministic polynomial time algorithm for this problem when the inputs are read-twice formulas. This algorithm also computes the MLIN predicate, testing if the input circuit computes a multilinear polynomial. We further study two related computational problems on arithmetic circuits. Given an arithmetic circuit C, 1) ZMC: test if a given monomial in C has zero coefficient or not, and 2) MonCount: compute the number of monomials in C. These problems were introduced by Fournier, Malod and Mengel [STACS 2012], and shown to characterize various levels of the counting hierarchy (CH). We address the above problems on read-restricted arithmetic circuits and branching programs. We prove several complexity characterizations for the above problems on these restricted classes of arithmetic circuits. © 2012 Springer-Verlag.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN03029743