Document Open Access Logo

Improved Low-Depth Set-Multilinear Circuit Lower Bounds

Authors Deepanshu Kush, Shubhangi Saraf

PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.38.pdf
  • Filesize: 0.67 MB
  • 16 pages

Document Identifiers

Author Details

Deepanshu Kush
  • Department of Computer Science, University of Toronto, Canada
Shubhangi Saraf
  • Department of Mathematics and Department of Computer Science, University of Toronto, Canada

Funding

  • Saraf, Shubhangi: Research partially supported by a Sloan research fellowship and an NSERC Discovery Grant.

Acknowledgements

We would like to thank Swastik Kopparty, Mrinal Kumar, and Ben Rossman for several helpful discussions.

Cite As Get BibTex

Deepanshu Kush and Shubhangi Saraf. Improved Low-Depth Set-Multilinear Circuit Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.38

Abstract

In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial f in VNP defined over n² variables, and of degree n, such that any product-depth Δ set-multilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). The hard polynomial f comes from the class of Nisan-Wigderson (NW) design-based polynomials. 
Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form (log n)^Ω(Δ n^{1/Δ}) was shown for the size of product-depth Δ set-multilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as f. Moreover, our lower bounds are novel for any Δ ≥ 2.
The precise quantitative expression in our lower bound is interesting also because the lower bounds we obtain are "sharp" in the sense that any asymptotic improvement would imply general set-multilinear circuit lower bounds via depth reduction results. 
In the setting of general set-multilinear formulas, a lower bound of the form n^Ω(log n) was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST (which extend the techniques of the same authors in (FOCS 2021)) give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form (log n)^Ω(log n) for the size of general set-multilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form n^Ω(log n), albeit for the same polynomial f in VNP (the NW polynomial). As observed by LST, if the same n^Ω(log n) size lower bounds for unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • algebraic circuit complexity
  • complexity measure
  • set-multilinear formulas

Metrics

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

Related Versions

References

  1. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 67-75. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.32.
  2. Miklós Ajtai. ∑^1_1-formulae on finite structures. Ann. Pure Appl. Log., 24(1):1-48, 1983. URL: https://doi.org/10.1016/0168-0072(83)90038-6.
  3. Peter Bürgisser. Cook’s versus valiant’s hypothesis. Theor. Comput. Sci., 235(1):71-88, 2000. URL: https://doi.org/10.1016/S0304-3975(99)00183-8.
  4. Suryajith Chillara, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. A near-optimal depth-hierarchy theorem for small-depth multilinear circuits. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 934-945. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00092.
  5. 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. URL: https://doi.org/10.1137/18M1191567.
  6. Zeev Dvir, Guillaume Malod, Sylvain Perifel, and Amir Yehudayoff. Separating multilinear branching programs and formulas. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 615-624. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214034.
  7. 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. URL: https://doi.org/10.1137/140990280.
  8. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory, 17(1):13-27, 1984. URL: https://doi.org/10.1007/BF01744431.
  9. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20. ACM, 1986. URL: https://doi.org/10.1145/12130.12132.
  10. Pavel Hrubes and Amir Yehudayoff. Homogeneous formulas and symmetric polynomials. Comput. Complex., 20(3):559-578, 2011. URL: https://doi.org/10.1007/s00037-011-0007-3.
  11. 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. URL: https://doi.org/10.1137/151002423.
  12. Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between read-once oblivious algebraic branching programs (roabps) and multilinear depth-three circuits. ACM Trans. Comput. Theory, 12(1):2:1-2:27, 2020. URL: https://doi.org/10.1145/3369928.
  13. Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 146-153. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591847.
  14. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. An almost cubic lower bound for depth three arithmetic circuits. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 33:1-33:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.33.
  15. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. On the size of homogeneous and of depth-four formulas with low individual degree. Theory Comput., 14(1):1-46, 2018. URL: https://doi.org/10.4086/toc.2018.v014a016.
  16. Pascal Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci., 448:56-65, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.041.
  17. Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. Towards optimal depth reductions for syntactically multilinear circuits. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 78:1-78:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.78.
  18. Mrinal Kumar and Ramprasad Saptharishi. Finer separations between shallow arithmetic circuits. In Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen, editors, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India, volume 65 of LIPIcs, pages 38:1-38:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.38.
  19. Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. SIAM J. Comput., 46(1):336-387, 2017. URL: https://doi.org/10.1137/140999335.
  20. Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 804-814. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00083.
  21. Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. To appear in STOC, 2022. URL: https://eccc.weizmann.ac.il/report/2021/094.
  22. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  23. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Comput. Complex., 6(3):217-234, 1997. URL: https://doi.org/10.1007/BF01294256.
  24. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2):8:1-8:17, 2009. URL: https://doi.org/10.1145/1502793.1502797.
  25. Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):40:1-40:15, 2013. URL: https://doi.org/10.1145/2535928.
  26. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Comput. Complex., 18(2):171-207, 2009. URL: https://doi.org/10.1007/s00037-009-0270-8.
  27. Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333-338, 1987. Google Scholar
  28. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github Survey, 2015. URL: https://github.com/dasarpmar/lowerbounds-survey.
  29. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77-82. ACM, 1987. URL: https://doi.org/10.1145/28395.28404.
  30. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2-11, 2015. URL: https://doi.org/10.1016/j.ic.2014.09.004.
  31. Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 1-10. IEEE Computer Society, 1985. URL: https://doi.org/10.1109/SFCS.1985.49.
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