2026-07-25T16:23:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6874 2024-03-06T10:39:05Z ddc:004 open_access

Sum of Products of Read-Once Formulas C., Ramya Rao, B. V. Raghavendra Arithmetic Circuits Permanent Computational Complexity Algebraic Complexity Theory 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ramya C. and B. V. Raghavendra Rao 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.39 urn:nbn:de:0030-drops-68741 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.39 eng https://creativecommons.org/licenses/by/3.0/legalcode