C., Ramya ;
Rao, B. V. Raghavendra
Sum of Products of ReadOnce Formulas
Abstract
We study limitations of polynomials computed by depth two circuits built over readonce formulas (ROFs). In particular,
1. We prove an exponential lower bound for the sum of ROFs computing the 2nvariate 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 nonmultilinear 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 nontrivial 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].
BibTeX  Entry
@InProceedings{c_et_al:LIPIcs:2016:6874,
author = {Ramya C. and B. V. Raghavendra Rao},
title = {{Sum of Products of ReadOnce Formulas}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {39:139:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6874},
URN = {urn:nbn:de:0030drops68741},
doi = {10.4230/LIPIcs.FSTTCS.2016.39},
annote = {Keywords: Arithmetic Circuits, Permanent, Computational Complexity, Algebraic Complexity Theory}
}
2016
Keywords: 

Arithmetic Circuits, Permanent, Computational Complexity, Algebraic Complexity Theory 
Seminar: 

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Issue date: 

2016 
Date of publication: 

2016 