Document Open Access Logo

On Algebraic Branching Programs of Small Width

Authors Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.20.pdf
  • Filesize: 0.67 MB
  • 31 pages

Document Identifiers

Author Details

Karl Bringmann
Christian Ikenmeyer
Jeroen Zuiddam

Cite AsGet BibTex

Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. On Algebraic Branching Programs of Small Width. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 20:1-20:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CCC.2017.20

Abstract

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar. As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.
Keywords
  • algebraic branching programs
  • algebraic complexity theory
  • border complexity
  • formula size
  • iterated matrix multiplication

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. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 67-75, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.32.
  2. Eric Allender and Fengming Wang. On the power of algebraic branching programs of width two. Comput. Complexity, 25(1):217-253, 2016. URL: http://dx.doi.org/10.1007/s00037-015-0114-7.
  3. Jarod Alper, Tristram Bogart, and Mauricio Velasco. A lower bound for the determinantal complexity of a hypersurface. Found. Comput. Math., pages 1-8, 2015. http://arxiv.org/abs/1505.02205, URL: http://dx.doi.org/10.1007/s10208-015-9300-x.
  4. Alexander E. Andreev. A method for obtaining more than quadratic effective lower estimates of complexity of π schemes. Moscow Univ. Math. Bull., 42(1):63-66, 1987. Google Scholar
  5. Daniel J. Bates and Luke Oeding. Toward a salmon conjecture. Exp. Math., 20(3):358-370, 2011. URL: http://dx.doi.org/10.1080/10586458.2011.576539.
  6. Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. Comput., 21(1):54-58, 1992. URL: http://dx.doi.org/10.1137/0221006.
  7. Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti. O(n^2.7799) complexity for n × n approximate matrix multiplication. Inf. Process. Lett., 8(5):234-235, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90113-3.
  8. Richard P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201-206, April 1974. URL: http://dx.doi.org/10.1145/321812.321815.
  9. Peter Bürgisser. Completeness and reduction in algebraic complexity theory, volume 7 of Algorithms Comput. Math. Springer-Verlag, Berlin, 2000. URL: http://dx.doi.org/10.1007/978-3-662-04179-6.
  10. Peter Bürgisser. The complexity of factors of multivariate polynomials. Found. Comput. Math., 4(4):369-396, 2004. URL: http://dx.doi.org/10.1007/s10208-002-0059-5.
  11. Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren Math. Wiss. Springer-Verlag, Berlin, 1997. URL: http://dx.doi.org/10.1007/978-3-662-03338-8.
  12. Peter Bürgisser and Christian Ikenmeyer. Geometric complexity theory and tensor rank. Proceedings 43rd Annual ACM Symposium on Theory of Computing 2011, pages 509-518, 2011. URL: http://dx.doi.org/10.1145/1993636.1993704.
  13. Peter Bürgisser and Christian Ikenmeyer. Explicit lower bounds via geometric complexity theory. Proceedings 45th Annual ACM Symposium on Theory of Computing 2013, pages 141-150, 2013. URL: http://dx.doi.org/10.1145/2488608.2488627.
  14. Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory. Proceedings IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 386-395, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.49.
  15. Peter Bürgisser, Joseph M. Landsberg, Laurent Manivel, and Jerzy Weyman. An overview of mathematical issues arising in the geometric complexity theory approach to VP≠VNP. SIAM J. Comput., 40(4):1179-1209, 2011. URL: http://dx.doi.org/10.1137/090765328.
  16. Klim Efremenko, Joseph M. Landsberg, Hal Schenck, and Jerzy Weyman. The method of shifted partial derivatives cannot separate the permanent from the determinant. ArXiv, 2016. URL: http://arxiv.org/abs/1609.02103.
  17. Michael Forbes. Some concrete questions on the border complexity of polynomials. Presentation given at the Workshop on Algebraic Complexity Theory WACT 2016 in Tel Aviv, https://www.youtube.com/watch?v=1HMogQIHT6Q, 2016.
  18. Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving algebraic circuits lower bounds. ArXiv, 2017. URL: http://arxiv.org/abs/1701.05328.
  19. Fulvio Gesmundo. Geometric aspects of iterated matrix multiplication. J. Algebra, 461:42-64, 2016. http://arxiv.org/abs/1512.00766, URL: http://dx.doi.org/10.1016/j.jalgebra.2016.04.028.
  20. Joshua A. Grochow. Unifying known lower bounds via geometric complexity theory. Comput. Complexity, 24(2):393-475, 2015. URL: http://dx.doi.org/10.1007/s00037-015-0103-x.
  21. Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of LIPIcs, pages 34:1-34:14, 2016. http://arxiv.org/abs/1605.02815, URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.34.
  22. Yonghui Guan. Brill’s equations as a GL(V)-module. ArXiv, 2015. URL: http://arxiv.org/abs/1508.02293.
  23. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. In 2013 IEEE Conference on Computational Complexity - CCC 2013, pages 65-73. IEEE Computer Soc., Los Alamitos, CA, 2013. URL: http://dx.doi.org/10.1109/CCC.2013.16.
  24. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: a chasm at depth three. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science - FOCS 2013, pages 578-587. IEEE Computer Soc., Los Alamitos, CA, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.68.
  25. Johan Håstad. The shrinkage exponent of De Morgan formulas is 2. SIAM J. Comput., 27(1):48-64, 1998. URL: http://dx.doi.org/10.1137/S0097539794261556.
  26. Jonathan D. Hauenstein, Christian Ikenmeyer, and Joseph M. Landsberg. Equations for lower bounds on border rank. Exp. Math., 22(4):372-383, 2013. URL: http://dx.doi.org/10.1080/10586458.2013.825892.
  27. Pavel Hrubeš and Iddo Tzameret. Short proofs for the determinant identities. SIAM J. Comput., 44(2):340-383, 2015. URL: http://dx.doi.org/10.1137/130917788.
  28. Russell Impagliazzo and Noam Nisan. The effect of random restrictions on formula size. Random Structures Algorithms, 4(2):121-133, 1993. URL: http://dx.doi.org/10.1002/rsa.3240040202.
  29. K. A. Kalorkoti. A lower bound for the formula size of rational functions. SIAM J. Comput., 14(3):678-687, 1985. URL: http://dx.doi.org/10.1137/0214050.
  30. Pascal Koiran. Arithmetic circuits: the chasm at depth four gets wider. Theoret. Comput. Sci., 448:56-65, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.041.
  31. Joseph M. Landsberg. The border rank of the multiplication of 2x2 matrices is seven. J. Amer. Math. Soc., 19(2):447-459, 2006. URL: http://dx.doi.org/10.1090/S0894-0347-05-00506-0.
  32. 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: http://dx.doi.org/10.4171/CMH/292.
  33. Joseph M. Landsberg and Mateusz Michałek. A 2n²-log(n)-1 lower bound for the border rank of matrix multiplication. arXiv, 2016. URL: http://arxiv.org/abs/1608.07486.
  34. Joseph M. Landsberg and Giorgio Ottaviani. New lower bounds for the border rank of matrix multiplication. Theory Comput., 11:285-298, 2015. http://arxiv.org/abs/1112.6007, URL: http://dx.doi.org/10.4086/toc.2015.v011a011.
  35. Thomas Lickteig. A note on border rank. Inf. Process. Lett., 18(3):173-178, 1984. URL: http://dx.doi.org/10.1016/0020-0190(84)90023-1.
  36. Guillaume Malod and Natacha Portier. Characterizing Valiant’s algebraic complexity classes. J. Complexity, 24(1):16-38, 2008. URL: http://dx.doi.org/10.1016/j.jco.2006.09.006.
  37. Thierry Mignon and Nicolas Ressayre. A quadratic bound for the determinant and permanent problem. Int. Math. Res. Not., 2004(79):4241-4253, 2004. URL: http://dx.doi.org/10.1155/S1073792804142566.
  38. Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory. I. An approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496-526, 2001. URL: http://dx.doi.org/10.1137/S009753970038715X.
  39. Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory II. Towards explicit obstructions for embeddings among class varieties. SIAM J. Comput., 38(3):1175-1206, 2008. URL: http://dx.doi.org/10.1137/080718115.
  40. Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410-418. ACM, 1991. URL: http://dx.doi.org/10.1145/103418.103462.
  41. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Comput. Complexity, 6(3):217-234, 1996/97. URL: http://dx.doi.org/10.1007/BF01294256.
  42. Luke Oeding and Steven V. Sam. Equations for the fifth secant variety of segre products of projective spaces. Exp. Math., 25(1):94-99, 2016. URL: http://dx.doi.org/10.1080/10586458.2015.1037872.
  43. Michael S. Paterson and Uri Zwick. Shrinkage of De Morgan formulae under restriction. Random Structures Algorithms, 4(2):135-150, 1993. URL: http://dx.doi.org/10.1002/rsa.3240040203.
  44. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2):Art. 8, 17, 2009. URL: http://dx.doi.org/10.1145/1502793.1502797.
  45. Herbert John Ryser. Combinatorial mathematics. The Carus Mathematical Monographs, No. 14. Published by The Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1963. Google Scholar
  46. Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. The power of depth 2 circuits over algebras. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, volume 4, pages 371-382, 2009. http://arxiv.org/abs/0904.2058, URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2333.
  47. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity 3.0.2, 2016. Online survey, URL: https://github.com/dasarpmar/lowerbounds-survey.
  48. Volker Strassen. Rank and optimal computation of generic tensors. Linear Algebra Appl., 52/53:645-685, 1983. URL: http://dx.doi.org/10.1016/0024-3795(83)80041-X.
  49. Bella Abramovna Subbotovskaya. Realizations of linear functions by formulas using +,⋅,-. Doklady Akademii Nauk SSSR, 136(3):553-555, 1961. Google Scholar
  50. Avishay Tal. Shrinkage of De Morgan formulae by spectral techniques. In 55th Annual IEEE Symposium on Foundations of Computer Science - FOCS, pages 551-560. IEEE Computer Soc., Los Alamitos, CA, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.65.
  51. Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inform. and Comput., 240:2-11, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.09.004.
  52. Seinosuke Toda. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Trans. Inf. &Syst., 75(1):116-124, 1992. Google Scholar
  53. Leslie G. Valiant. Completeness classes in algebra. In Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979), pages 249-261. ACM, New York, 1979. URL: http://dx.doi.org/10.1145/800135.804419.
  54. Leslie G. Valiant. Reducibility by algebraic projections. University of Edinburgh, Department of Computer Science, 1980. Internal Report. Google Scholar
  55. Jeroen Zuiddam. A note on the gap between rank and border rank. Linear Algebra Appl., 525:33-44, 2017. http://arxiv.org/abs/1504.05597, URL: http://dx.doi.org/10.1016/j.laa.2017.03.015.
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