License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.39
URN: urn:nbn:de:0030-drops-68741
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6874/
Go to the corresponding LIPIcs Volume Portal

C., Ramya ; Rao, B. V. Raghavendra

Sum of Products of Read-Once Formulas

pdf-format:
LIPIcs-FSTTCS-2016-39.pdf (0.6 MB)

Abstract

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].

BibTeX - Entry

@InProceedings{c_et_al:LIPIcs:2016:6874,
  author =	{Ramya C. and B. V. Raghavendra Rao},
  title =	{{Sum of Products of Read-Once Formulas}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6874},
  URN =		{urn:nbn:de:0030-drops-68741},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.39},
  annote =	{Keywords: Arithmetic Circuits, Permanent, Computational Complexity, Algebraic Complexity Theory}
}

Keywords: Arithmetic Circuits, Permanent, Computational Complexity, Algebraic Complexity Theory
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI