Name
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2014.01.005 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
input circuit,identically zero,arithmetic circuit,related computational problem,read-restricted arithmetic circuit,complexity characterisations,zero coefficient,simple read-restricted circuit,deterministic polynomial time algorithm,arithmetic circuit C,identity testing,multilinear polynomial | Journal | 524, |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.36 |
References | Authors | |
16 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| B. V. Raghavendra Rao | 2 | 53 | 13.86 |
| Karteek Sreenivasaiah | 3 | 13 | 5.30 |