Raghavendra Rao B. V.

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.

We study limitations of polynomials computed by depth two circuits built over read-once formulas (ROFs). In particular, 1. We prove an exponential lower bound for the sum of ROFs computing the 2n-variate polynomial in VP defined by Raz and Yehudayoff [CC,2009]. 2. We obtain an exponential lower bound on the size of arithmetic circuits computing sum of products of restricted ROFs of unbounded depth computing the permanent of an n by n matrix. The restriction is on the number of variables with + gates as a parent in a proper sub formula of the ROF to be bounded by sqrt(n). Additionally, we restrict the product fan in to be bounded by a sub linear function. This proves an exponential lower bound for a subclass of possibly non-multilinear formulas of unbounded depth computing the permanent polynomial. 3. We also show an exponential lower bound for the above model against a polynomial in VP. 4. Finally we observe that the techniques developed yield an exponential lower bound on the size of sums of products of syntactically multilinear arithmetic circuits computing a product of variable disjoint linear forms where the bottom sum gate and product gates at the second level have fan in bounded by a sub linear function. Our proof techniques are built on the measure developed by Kumar et. al.[ICALP 2013] and are based on a non-trivial analysis of ROFs under random partitions. Further, our results exhibit strengths and provide more insight into the lower bound techniques introduced by Raz [STOC 2004].

Polynomial Identity Testing (PIT) algorithms have focussed on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are the simplest of read-restricted polynomials. Building structures above these, we show the following: (1) a deterministic polynomial-time non-black-box PIT algorithm for ∑ (2)× ∏ × ROF. (2) Weak hardness of representation theorems for sums of powers of constant-free ROPs and for ROFs of the form ∑ × ∏ × ∑. (3) A partial characterization of multilinear monotone constant-free ROPs.