Header menu link for other important links
X
Monomials, multilinearity and identity testing in simple read-restricted circuits
Published in
2014
Volume: 524
   
Pages: 90 - 102
Abstract
We study the problem of testing if the polynomial computed by an arithmetic circuit is identically zero. We give a deterministic polynomial time algorithm for this problem when the inputs are read-twice or read-thrice formulas. In the process, these algorithms also test if the input circuit is computing a multilinear polynomial. We further study three 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, (2) MonCount: compute the number of monomials in C, and (3) MLIN: test if C computes a multilinear polynomial or not. These problems were introduced by Fournier, Malod and Mengel (2012) [11], and shown to characterise various levels of the counting hierarchy (CH). We address the above problems on read-restricted arithmetic circuits and branching programs. We prove several complexity characterisations for the above problems on these restricted classes of arithmetic circuits. © 2014 Elsevier B.V.
About the journal
JournalTheoretical Computer Science
ISSN03043975
Open AccessYes
Concepts (10)
  •  related image
    Arithmetic circuit
  •  related image
    Branching programs
  •  related image
    COMPUTATIONAL PROBLEM
  •  related image
    IDENTITY TESTING
  •  related image
    MULTILINEAR POLYNOMIALS
  •  related image
    Polynomial-time algorithms
  •  related image
    Computational complexity
  •  related image
    Integrating circuits
  •  related image
    Polynomial approximation
  •  related image
    Logic circuits