Lower bounds for Sum and Sum of Products of Read-once Formulas

摘要

We study limitations of polynomials computed by depth-2 circuits built over read-once formulas (ROFs). In particular: 1. We prove a 2~(Ω(n)) lower bound for the sum of ROFs computing the 2n-variate polynomial in VP defined by Raz and Yehudayoff [21]. 2. We obtain a 2~(Ω(√n)) lower bound on the size of ΣП~([n~(1/15)]) arithmetic circuits built over restricted ROFs of unbounded depth computing the permanent of an n × n matrix (superscripts on gates denote bound on the fan-in). The restriction is that the number of variables with + gates as a parent in a proper sub formula of the ROF has to be bounded by √n 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 ΣП~([N~(1/30)]) arithmetic circuits built over syntactically multi-linear ΣПΣ~([N(1/4)]) arithmetic circuits computing a product of variable disjoint linear forms on N variables, where the superscripts on gates denote bound on the fan-in. Our proof techniques are built on the measure developed by Kumar et al. [14] 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 [19].