Document Open Access Logo

On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

Author Suryajith Chillara

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.47.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Suryajith Chillara
  • CRI, University of Haifa, Israel

Funding

The author was supported by the Institite Post Doctoral Fellowship at IIT Bombay where a part of this work was done. The author is currently supported by a CHE-PBC (VATAT) fellowship at University of Haifa. The author is also affiliated to Caesarea Rothschild Institute at University of Haifa.

Acknowledgements

The author is grateful to Nutan Limaye and Srikanth Srinivasan for their invaluable feedback.

Cite AsGet BibTex

Suryajith Chillara. On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.47

Abstract

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of r (referred to as multi-r-ic circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better and better bounds as the value of r increases. Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree r computing a multilinear polynomial on n^O(1) variables and degree d=o(n), must have size at least (n/r^1.1)^Ω(√{d/r}) when r is o(d) and is strictly less than n^1.1. This bound however deteriorates with increasing r. It is a natural question to ask if we can prove a bound that does not deteriorate with increasing r or a bound that holds for a larger regime of r. We here prove a lower bound which does not deteriorate with r, however for a specific instance of d = d(n) but for a wider range of r. Formally, we show that there exists an explicit polynomial on n^O(1) variables and degree Θ(log² n) such that any depth four circuit of bounded individual degree r<n^0.2 must have size at least exp(Ω(log² n)). This improvement is obtained by suitably adapting the complexity measure of Kayal et al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et al. (SIAM J. Computing, 2017).

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Algebraic complexity theory
Keywords
  • Lower Bounds
  • Multilinear
  • Multi-r-ic

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 proceedings of Foundations of Computer Science (FOCS), pages 67-75, 2008. URL: https://doi.org/10.1109/FOCS.2008.32.
  2. Noga Alon, Mrinal Kumar, and Ben Lee Volk. Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. In CCC, volume 102 of LIPIcs, pages 11:1-11:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  3. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theor. Comput. Sci., 22:317-330, 1983. Google Scholar
  4. Suryajith Chillara, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. A near-optimal depth-hierarchy theorem for small-depth multilinear circuits. In FOCS, pages 934-945. IEEE Computer Society, 2018. Google Scholar
  5. Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. A quadratic size-hierarchy theorem for small-depth multilinear formulas. In ICALP, volume 107 of LIPIcs, pages 36:1-36:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  6. Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications. SIAM J. Comput., 48(1):70-92, 2019. Google Scholar
  7. Suryajith Chillara and Partha Mukhopadhyay. Depth-4 lower bounds, determinantal complexity: A unified approach. computational complexity, May 2019. URL: https://doi.org/10.1007/s00037-019-00185-4.
  8. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth-4 formulas computing iterated matrix multiplication. SIAM J. Comput., 44(5):1173-1201, 2015. Google Scholar
  9. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. Journal of the ACM (JACM), 61(6):33, 2014. Google Scholar
  10. Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory, 2019. URL: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/.
  11. Sumant Hegde and Chandan Saha. Improved lower bound for multi-r-ic depth four circuits as a function of the number of input variables. Proceedings of the Indian National Science Academy, 83(4):907-922, 2017. Google Scholar
  12. Pavel Hrubeš and Amir Yehudayoff. Homogeneous formulas and symmetric polynomials. Computational Complexity, 20(3):559-578, 2011. Google Scholar
  13. K. Kalorkoti. A lower bound for the formula size of rational functions. SIAM J. Comput., 14(3):678-687, 1985. Google Scholar
  14. 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
  15. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In STOC, pages 119-127. ACM, 2014. Google Scholar
  16. Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. SIAM J. Comput., 46(1):307-335, 2017. Google Scholar
  17. Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In proceedings of Symposium on Theoretical Aspects of Computer Science (STACS), pages 46:1-46:15, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.46.
  18. Neeraj Kayal and Chandan Saha. Multi-k-ic depth three circuit lower bound. Theory Comput. Syst., 61(4):1237-1251, 2017. Google Scholar
  19. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In STOC, pages 146-153. ACM, 2014. Google Scholar
  20. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. On the size of homogeneous and of depth-four formulas with low individual degree. Theory of Computing, 14(16):1-46, 2018. URL: https://doi.org/10.4086/toc.2018.v014a016.
  21. Mrinal Kumar, Rafael Mendes de Oliveira, and Ramprasad Saptharishi. Towards optimal depth reductions for syntactically multilinear circuits. In ICALP, volume 132 of LIPIcs, pages 78:1-78:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  22. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. SIAM J. Comput., 46(1):336-387, 2017. Google Scholar
  23. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. URL: https://doi.org/10.1007/BF01294256.
  24. Ran Raz. Multilinear-NC² ≠ multilinear-NC^1. In proceedings of Foundations of Computer Science (FOCS), pages 344-351, 2004. URL: https://doi.org/10.1109/FOCS.2004.42.
  25. Ran Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(1):121-135, 2006. URL: https://doi.org/10.4086/toc.2006.v002a006.
  26. Ran Raz, Amir Shpilka, and Amir Yehudayoff. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM Journal of Computing, 38(4):1624-1647, 2008. URL: https://doi.org/10.1137/070707932.
  27. Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17(4):515-535, 2008. URL: https://doi.org/10.1007/s00037-008-0254-0.
  28. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171-207, 2009. URL: https://doi.org/10.1007/s00037-009-0270-8.
  29. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity version 8.0.4. Github survey, 2019. URL: https://github.com/dasarpmar/lowerbounds-survey/releases/.
  30. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5:207-388, March 2010. URL: https://doi.org/10.1561/0400000039.
  31. Volker Strassen. Berechnungen in partiellen algebren endlichen typs. Computing, 11(3):181-196, 1973. Google Scholar
  32. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Information and Computation, 240:2-11, 2015. URL: https://doi.org/10.1016/j.ic.2014.09.004.
  33. Leslie G. Valiant. Completeness classes in algebra. In STOC, pages 249-261. ACM, 1979. Google Scholar
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 Imprint Privacy Contact