Rabbits Approximate, Cows Compute Exactly!

Authors Balagopal Komarath, Anurag Pandey, Nitin Saurabh



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.65.pdf
  • Filesize: 0.66 MB
  • 14 pages

Document Identifiers

Author Details

Balagopal Komarath
  • IIT Gandhinagar, India
Anurag Pandey
  • Department of Computer Science, Saarland University, Saarland Informatics Campus, Germany
Nitin Saurabh
  • Department of Computer Science and Engineering, IIT Hyderabad, India

Acknowledgements

We thank Arkadev Chattopadhyay for herding us towards this beautiful problem and sharing his insights! We also thank Meena Mahajan for bringing the reference [E. Allender et al., 2003] to our notice. We also thank the organizers of GCT2022 workshop for hosting a talk by Avi Wigderson which prompted us towards this investigation. We thank anonymous reviewers for helpful suggestions.

Cite AsGet BibTex

Balagopal Komarath, Anurag Pandey, and Nitin Saurabh. Rabbits Approximate, Cows Compute Exactly!. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.65

Abstract

Valiant, in his seminal paper in 1979, showed an efficient simulation of algebraic formulas by determinants, showing that VF, the class of polynomial families computable by polynomial-sized algebraic formulas, is contained in VDet, the class of polynomial families computable by polynomial-sized determinants. Whether this containment is strict has been a long-standing open problem. We show that algebraic formulas can in fact be efficiently simulated by the determinant of tetradiagonal matrices, transforming the open problem into a problem about determinant of general matrices versus determinant of tetradiagonal matrices with just three non-zero diagonals. This is also optimal in a sense that we cannot hope to get the same result for matrices with only two non-zero diagonals or even tridiagonal matrices, thanks to Allender and Wang (Computational Complexity'16) which showed that the determinant of tridiagonal matrices cannot even compute simple polynomials like x_1 x_2 + x_3 x_4 + ⋯ + x_15 x_16. Our proof involves a structural refinement of the simulation of algebraic formulas by width-3 algebraic branching programs by Ben-Or and Cleve (SIAM Journal of Computing'92). The tetradiagonal matrices we obtain in our proof are also structurally very similar to the tridiagonal matrices of Bringmann, Ikenmeyer and Zuiddam (JACM'18) which showed that, if we allow approximations in the sense of geometric complexity theory, algebraic formulas can be efficiently simulated by the determinant of tridiagonal matrices of a very special form, namely the continuant polynomial. The continuant polynomial family is closely related to the Fibonacci sequence, which was used to model the breeding of rabbits. The determinants of our tetradiagonal matrices, in comparison, is closely related to Narayana’s cows sequences, which was originally used to model the breeding of cows. Our result shows that the need for approximation can be eliminated by using Narayana’s cows polynomials instead of continuant polynomials, or equivalently, shifting one of the outer diagonals of a tridiagonal matrix one place away from the center. Conversely, we observe that the determinant (or, permanent) of band matrices can be computed by polynomial-sized algebraic formulas when the bandwidth is bounded by a constant, showing that the determinant (or, permanent) of bandwidth k matrices for all constants k ≥ 2 yield VF-complete polynomial families. In particular, this implies that the determinant of tetradiagonal matrices in general and Narayana’s cows polynomials in particular yield complete polynomial families for the class VF.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Circuit complexity
Keywords
  • Algebraic complexity theory
  • Algebraic complexity classes
  • Determinant versus permanent
  • Algebraic formulas
  • Algebraic branching programs
  • Band matrices
  • Tridiagonal matrices
  • Tetradiagonal matrices
  • Continuant
  • Narayana’s cow sequence
  • Padovan sequence

Metrics

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

References

  1. OEIS Foundation Inc. (2022). Narayana’s Cows Sequence, Entry A000930 in the On-Line Encyclopedia of Integer Sequences. https://oeis.org/A000930, 1964. Accessed: 2022-04-26.
  2. OEIS Foundation Inc. (2022). Padovan Sequence, Entry A000931 in the On-Line Encyclopedia of Integer Sequences. https://oeis.org/A000931, 1964. Accessed: 2022-04-26.
  3. E. Allender, V. Arvind, and M. Mahajan. Arithmetic complexity, kleene closure, and formal power series. Theory Comput. Syst., 36(4):303-328, 2003. Google Scholar
  4. E. Allender and F. Wang. On the power of algebraic branching programs of width two. Comput. Complex., 25(1):217-253, 2016. Google Scholar
  5. M. Ben-Or and R. Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. Comput., 21(1):54-58, 1992. Google Scholar
  6. S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18(3):147-150, 1984. Google Scholar
  7. R. P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201-206, 1974. Google Scholar
  8. K. Bringmann, C. Ikenmeyer, and J. Zuiddam. On algebraic branching programs of small width. J. ACM, 65(5):32:1-32:29, 2018. Google Scholar
  9. C. Conley and V. Ovsienko. Lagrangian Configurations and Symplectic Cross-Ratios. Mathematische Annalen, pages 1105-1145, 2018. Google Scholar
  10. C. Conley and V. Ovsienko. Rotundus: Triangulations, Chebyshev Polynomials, and Pfaffians. Math Intelligencer, 40:45-50, 2018. Google Scholar
  11. L. Csanky. Fast parallel matrix inversion algorithms. SIAM Journal on Computing, 5(4):618-623, 1976. Google Scholar
  12. B. Grenet. An Upper Bound for the Permanent versus Determinant Problem. Manuscript, 2011. Google Scholar
  13. B. Komarath, A. Pandey, and N. Saurabh. Rabbits approximate, cows compute exactly! Manuscript, 2022. URL: https://nitinsau.github.io/pubs/cow-sequences.pdf.
  14. X. Lin. On the Recurrence Properties of Narayana’s Cows Sequence. Symmetry, 13(1), 2021. URL: https://www.mdpi.com/2073-8994/13/1/149.
  15. M. Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Electron. Colloquium Comput. Complex., 4, 1997. Google Scholar
  16. S. Morier-Genoud. Coxeter’s Frieze Patterns at the Crossroads of Algebra, Geometry and Combinatorics. Bulletin of the London Mathematical Society, 47(6):895-938, 2015. Google Scholar
  17. S. Morier-Genoud and V. Ovsienko. Farey Boat: Continued Fractions and Triangulations, Modular Group and Polygon Dissections. Jahresber. Dtsch. Math. Ver., 121:91-136, 2019. Google Scholar
  18. Narayana Pandita. Ganita Kaumudi, 1356. India. Google Scholar
  19. I. Stewart. Tales of a neglected number. Scientific American, 274(6):102-103, 1996. URL: http://www.jstor.org/stable/24989576.
  20. L. G. Valiant. Completeness Classes in Algebra. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 249-261, 1979. Google Scholar
  21. Wikipedia contributors. Narayana Pandita (mathematician). https://en.wikipedia.org/w/index.php?title=Narayana_Pandita_(mathematician)&oldid=1071293682, 2022. [Online; accessed 26-April-2022].
  22. Wikipedia contributors. Padovan Polynomials. https://en.wikipedia.org/w/index.php?title=Padovan_polynomials&oldid=1080802324, 2022. [Online; accessed 27-April-2022].
  23. Wikipedia contributors. Padovan Sequence. https://en.wikipedia.org/w/index.php?title=Padovan_sequence&oldid=1078995920, 2022. [Online; accessed 27-April-2022].
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