Komarath, Balagopal ;
Pandey, Anurag ;
Saurabh, Nitin
Rabbits Approximate, Cows Compute Exactly!
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 polynomialsized algebraic formulas, is contained in VDet, the class of polynomial families computable by polynomialsized determinants. Whether this containment is strict has been a longstanding 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 nonzero diagonals. This is also optimal in a sense that we cannot hope to get the same result for matrices with only two nonzero 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 width3 algebraic branching programs by BenOr 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 polynomialsized 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 VFcomplete 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.
BibTeX  Entry
@InProceedings{komarath_et_al:LIPIcs.MFCS.2022.65,
author = {Komarath, Balagopal and Pandey, Anurag and Saurabh, Nitin},
title = {{Rabbits Approximate, Cows Compute Exactly!}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {65:165:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16863},
URN = {urn:nbn:de:0030drops168637},
doi = {10.4230/LIPIcs.MFCS.2022.65},
annote = {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}
}
22.08.2022
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 
Seminar: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Issue date: 

2022 
Date of publication: 

22.08.2022 