Name
Title | ||
|---|---|---|
Identity testing, multilinearity testing, and monomials in read-once/twice formulas and branching programs |
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-32589-2_57 | MFCS |
Keywords | Field | DocType |
arithmetic circuit,identically zero,deterministic polynomial time algorithm,identity testing,input circuit,read-restricted arithmetic circuit,related computational problem,mlin predicate,zero coefficient,multilinearity testing,arithmetic circuit c,twice formula,multilinear polynomial | Discrete mathematics,Computational problem,Combinatorics,Polynomial,Predicate (grammar),Monomial,Hierarchy,Arithmetic circuit complexity,Time complexity,Mathematics,Branching (version control) | Conference |
Volume | ISSN | Citations |
7464 | 0302-9743 | 2 |
PageRank | References | Authors |
0.37 | 13 | 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 |