Document Open Access Logo

A Lower Bound on Determinantal Complexity

Authors Mrinal Kumar, Ben Lee Volk

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2021.4.pdf
  • Filesize: 0.65 MB
  • 12 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Circuit complexity
Keywords
  • Determinantal Complexity
  • Algebraic Circuits
  • Lower Bounds
  • Singular Variety

Metrics

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

Abstract

The determinantal complexity of a polynomial P ∈ 𝔽[x₁, …, x_n] over a field 𝔽 is the dimension of the smallest matrix M whose entries are affine functions in 𝔽[x₁, …, x_n] such that P = Det(M). We prove that the determinantal complexity of the polynomial ∑_{i = 1}^n x_i^n is at least 1.5n - 3. 
For every n-variate polynomial of degree d, the determinantal complexity is trivially at least d, and it is a long standing open problem to prove a lower bound which is super linear in max{n,d}. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than max{n,d}, and improves upon the prior best bound of n + 1, proved by Alper, Bogart and Velasco [Jarod Alper et al., 2017] for the same polynomial.

Cite As Get BibTex

Mrinal Kumar and Ben Lee Volk. A Lower Bound on Determinantal Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CCC.2021.4

Author Details

Mrinal Kumar
  • Department of Computer Science and Engineering, IIT Bombay, India
Ben Lee Volk
  • Department of Computer Science, University of Texas at Austin, TX, USA

Acknowledgements

Mrinal thanks Ramprasad Saptharishi for various discussions on determinantal complexity over the years, and in particular for explaining the proof of the result of Mignon and Ressayre to him.

References

  1. Boris Alexeev, Michael A. Forbes, and Jacob Tsimerman. Tensor rank: Some lower and upper bounds. In Proceedings of the 26th Annual Computational Complexity Conference (CCC 2011), pages 283-291. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/CCC.2011.28.
  2. Jarod Alper, Tristram Bogart, and Mauricio Velasco. A lower bound for the determinantal complexity of a hypersurface. Found. Comput. Math., 17(3):829-836, 2017. URL: https://doi.org/10.1007/s10208-015-9300-x.
  3. Markus Bläser. A 5/2 n²-lower bound for the rank of n × n matrix multiplication over arbitrary fields. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1999), pages 45-50, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814576.
  4. Mark R. Brown and David P. Dobkin. An improved lower bound on polynomial multiplication. IEEE Trans. Computers, 29(5):337-340, 1980. URL: https://doi.org/10.1109/TC.1980.1675583.
  5. Jin-Yi Cai. A note on the determinant and permanent problem. Inf. Comput., 84(1):119-127, 1990. URL: https://doi.org/10.1016/0890-5401(90)90036-H.
  6. Jin-Yi Cai, Xi Chen, and Dong Li. Quadratic lower bound for permanent vs. determinant in any characteristic. Comput. Complex., 19(1):37-56, 2010. URL: https://doi.org/10.1007/s00037-009-0284-2.
  7. Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A quadratic lower bound for algebraic branching programs. CoRR, abs/1911.11793, 2019. URL: http://arxiv.org/abs/1911.11793.
  8. Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity. Foundations and Trends in Theoretical Computer Science, 2011. URL: https://doi.org/10.1561/0400000043.
  9. David A. Cox, John B. Little, and Donal O'Shea. Ideals, Varieties and Algorithms. Undergraduate texts in mathematics. Springer, 2007. URL: https://doi.org/10.1007/978-0-387-35651-8.
  10. Joe Harris. Algebraic geometry, volume 133 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. A first course, Corrected reprint of the 1992 original. URL: https://doi.org/10.1007/978-1-4757-2189-8.
  11. Christian Ikenmeyer and J.M. Landsberg. On the complexity of the permanent in various computational models. Journal of Pure and Applied Algebra, 221(12):2911-2927, 2017. URL: https://doi.org/10.1016/j.jpaa.2017.02.008.
  12. Kyriakos Kalorkoti. A Lower Bound for the Formula Size of Rational Functions. SICOMP, 14(3):678-687, 1985. URL: https://doi.org/10.1137/0214050.
  13. Mrinal Kumar. A quadratic lower bound for homogeneous algebraic branching programs. Computational Complexity, 28(3):409-435, 2019. URL: https://doi.org/10.1007/s00037-019-00186-3.
  14. J.M. Landsberg and Nicolas Ressayre. Permanent v. determinant: An exponential lower bound assuming symmetry and a potential path towards valiant’s conjecture. Differential Geometry and its Applications, 55:146-166, 2017. URL: https://doi.org/10.1016/j.difgeo.2017.03.017.
  15. Joseph M. Landsberg, Laurent Manivel, and Nicolas Ressayre. Hypersurfaces with degenerate duals and the geometric complexity theory program. Comment. Math. Helv., 88(2):469-484, 2013. URL: https://doi.org/10.4171/CMH/292.
  16. Marvin Marcus and Henryk Minc. On the relation between the determinant and the permanent. Illinois J. Math., 5(3):376-381, September 1961. URL: https://doi.org/10.1215/ijm/1255630882.
  17. Roy Meshulam. On two extremal matrix problems. Linear Algebra and its Applications, 114-115:261-271, 1989. URL: https://www.sciencedirect.com/science/article/pii/0024379589904655.
  18. Thierry Mignon and Nicolas Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notes, 2004(79):4241-4253, 2004. Available on http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.4910. URL: https://doi.org/10.1155/S1073792804142566.
  19. George Pólya. Aufgabe 424. Archiv der Mathematik und Physik, 20:271, 1913. URL: http://babel.hathitrust.org/cgi/pt?id=mdp.39015085215716;seq=399.
  20. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015. URL: https://github.com/dasarpmar/lowerbounds-survey/releases/.
  21. Amir Shpilka. Lower bounds for matrix product. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2001), pages 358-367, 2001. URL: https://doi.org/10.1109/SFCS.2001.959910.
  22. 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.
  23. Gábor Szegő. Lösung zu aufgabe 424. Archiv der Mathematik und Physik, 21:291-292, 1913. URL: http://hdl.handle.net/2027/uc1.b2958231.
  24. Leslie G. Valiant. Completeness Classes in Algebra. In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC 1979), pages 249-261, 1979. URL: https://doi.org/10.1145/800135.804419.
  25. Joachim von zur Gathen. Permanent and determinant. Linear Algebra and its Applications, 96:87-100, 1987. URL: https://core.ac.uk/download/pdf/82095887.pdf.
  26. Akihiro Yabe. Bi-polynomial rank and determinantal complexity. CoRR, abs/1504.00151, 2015. URL: http://arxiv.org/abs/1504.00151.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact