Document Open Access Logo

Sum of Products of Read-Once Formulas

Authors Ramya C., B. V. Raghavendra Rao

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.39.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Ramya C.
B. V. Raghavendra Rao

Cite As Get BibTex

Ramya C. and B. V. Raghavendra Rao. Sum of Products of Read-Once Formulas. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.39

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

Subject Classification

Keywords
  • Arithmetic Circuits
  • Permanent
  • Computational Complexity
  • Algebraic Complexity Theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In FOCS, pages 67-75, 2008. http://dx.doi.org/10.1109/FOCS.
  2. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theor. Comput. Sci., 22:317-330, 1983. URL: http://dx.doi.org/10.1016/0304-3975(83)90110-X.
  3. Devdatt Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2009. Google Scholar
  4. Michael Forbes. Polynomial identity testing of read-once oblivious algebraic branching programs. PhD thesis, Massachusetts Institute of Technology, 2014. Google Scholar
  5. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 243-252, 2013. Google Scholar
  6. Dima Grigoriev and Marek Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In STOC, pages 577-582, 1998. URL: http://dx.doi.org/10.1145/276698.276872.
  7. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. J. ACM, 61(6):33:1-33:16, 2014. URL: http://dx.doi.org/10.1145/2629541.
  8. Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19:81, 2012. Google Scholar
  9. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In STOC, pages 119-127, 2014. URL: http://dx.doi.org/10.1145/2591796.2591823.
  10. Neeraj Kayal and Chandan Saha. Multi-k-ic depth three circuit lower bound. In STACS, pages 527-539, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.527.
  11. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. An almost cubic lower bound for depth three arithmetic circuits. Electronic Colloquium on Computational Complexity (ECCC), 23:6, 2016. Accepted at ICALP 2016. URL: http://eccc.hpi-web.de/report/2016/006.
  12. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci., 448:56-65, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.041.
  13. Mrinal Kumar, Gaurav Maheshwari, and Jayalal Sarma. Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices. TOCT, 8(3):8, 2016. URL: http://dx.doi.org/10.1145/2898437.
  14. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In FOCS, pages 364-373, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.46.
  15. Meena Mahajan and Anuj Tawari. Sums of read-once formulas: How many summands suffice? In Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings, pages 266-279, 2016. URL: http://dx.doi.org/10.1007/978-3-319-34171-2_19.
  16. Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410-418, 1991. URL: http://dx.doi.org/10.1145/103418.103462.
  17. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. URL: http://dx.doi.org/10.1007/BF01294256.
  18. C. Ramya and B. V. Raghavendra Rao. Limitations of sum of products of read-once polynomials. CoRR, abs/1512.03607, 2015. URL: https://arxiv.org/abs/1512.03607.
  19. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2), 2009. URL: http://dx.doi.org/10.1145/1502793.1502797.
  20. Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17(4):515-535, 2008. Google Scholar
  21. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171-207, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0270-8.
  22. Amir Shpilka and Ilya Volkovich. Read-once polynomial identity testing. Computational Complexity, 24(3):477-532, 2015. URL: http://dx.doi.org/10.1007/s00037-015-0105-8.
  23. Amir Shpilka and Avi Wigderson. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity, 10(1):1-27, 2001. URL: http://dx.doi.org/10.1007/PL00001609.
  24. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2-11, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.09.004.
  25. Iddo Tzameret. Studies in algebraic and propositional proof complexity. Ph.D Thesis, page 33, 2008. URL: http://www.cs.rhul.ac.uk/home/tzameret/Iddo-PhD-thesis.pdf.
  26. Leslie G. Valiant. Completeness classes in algebra. In STOC, pages 249-261, 1979. URL: http://dx.doi.org/10.1145/800135.804419.
  27. Ilya Volkovich. Characterizing arithmetic read-once formulae. TOCT, 8(1):2, 2016. URL: http://dx.doi.org/10.1145/2858783.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact