Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-201 | 9th March 2016 17:07

Limitations of sum of products of Read-Once Polynomials

RSS-Feed




Revision #1
Authors: C Ramya, Raghavendra Rao B V
Accepted on: 9th March 2016 17:07
Downloads: 896
Keywords: 


Abstract:

We study limitations of polynomials computed by depth two circuits built over read-once polynomials (ROPs) and depth three syntactically multi-linear formulas.
We prove an exponential lower bound for the size of the $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over syntactically multi-linear $\Sigma\Pi\Sigma^{[N^{8/15}]}$ arithmetic circuits computing a product of variable disjoint linear forms on $N$ variables. We extend the result to the case of $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over ROPs of unbounded depth, where the number of variables with $+$ gates as a parent in an proper sub formula is bounded by $N^{1/2+1/30}$. We show that the same lower bound holds for the permanent polynomial. Finally we obtain an exponential lower bound for the sum of ROPs computing a polynomial in ${ VP}$ defined by Raz and Yehudayoff~\cite{RY09}.


Our results demonstrate a class of formulas of unbounded depth with exponential size lower bound against the permanent and can be seen as an exponential improvement over the multilinear formula size lower bounds given by Raz~\cite{Raz04a} for a sub-class of multi-linear and non-multi-linear formulas.
Our proof techniques are built on the one developed by Raz~\cite{Raz04a} and later extended by Kumar et. al.~\cite{KMS13} and are based on non-trivial analysis of ROPs under random partitions. Further, our results exhibit strengths and limitations of the lower bound techniques introduced by Raz~\cite{Raz04a}.



Changes to previous version:

Errors in Proofs of Lemma 7 and 15 of the previous version have been fixed in this version


Paper:

TR15-201 | 10th December 2015 10:36

Limitations of sum of products of Read-Once Polynomials





TR15-201
Authors: C Ramya, Raghavendra Rao B V
Publication: 10th December 2015 16:16
Downloads: 1086
Keywords: 


Abstract:

We study limitations of polynomials computed by depth two circuits built over read-once polynomials (ROPs) and depth three syntactically multi-linear formulas.
We prove an exponential lower bound for the size of the $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over syntactically multi-linear $\Sigma\Pi\Sigma^{[N^{8/15}]}$ arithmetic circuits computing a product of variable disjoint linear forms on $N$ variables. We extend the result to the case of $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over ROPs of unbounded depth, where the number of variables with $+$ gates as a parent in an proper sub formula is bounded by $N^{1/2+1/30}$. We show that the same lower bound holds for the permanent polynomial. Finally we obtain an exponential lower bound for the sum of ROPs computing a polynomial in ${ VP}$ defined by Raz and Yehudayoff~\cite{RY09}.


Our results demonstrate a class of formulas of unbounded depth with exponential size lower bound against the permanent and can be seen as an exponential improvement over the multilinear formula size lower bounds given by Raz~\cite{Raz04a} for a sub-class of multi-linear and non-multi-linear formulas.
Our proof techniques are built on the one developed by Raz~\cite{Raz04a} and later extended by Kumar et. al.~\cite{KMS13} and are based on non-trivial analysis of ROPs under random partitions. Further, our results exhibit strengths and limitations of the lower bound techniques introduced by Raz~\cite{Raz04a}.



ISSN 1433-8092 | Imprint