Border Complexity of Symbolic Determinant under Rank One Restriction
Preprint
Abstract
VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_0 + \sum_{i=1}^n A_ix_i$ where the size of each $A_i$ is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem in geometric complexity theory (GCT) is to determine whether VBP is closed under approximation. The power of approximation is well understood for some restricted models of computation, e.g., the class of depth-two circuits, read-once oblivious ABPs (ROABP), monotone ABPs, depth-three circuits of bounded top fan-in, and width-two ABPs. The former three classes are known to be closed under approximation [Bl"{a}ser, Ikenmeyer, Mahajan, Pandey, and Saurabh (2020)], whereas the approximative closure of the last one captures the whole class of polynomial families computable by polynomial-sized formulas [Bringmann, Ikenmeyer, and Zuiddam (2017)]. In this work, we consider the subclass of VBP computed by the determinant of a symbolic matrix of the form $A_0 + \sum_{i=1}^n A_ix_i$ where for each $1\leq i \leq n$, $A_i$ is of rank one. It has been studied extensively [Edmonds(1968), Edmonds(1979)] and efficient identity testing algorithms are known [Lov"{a}sz (1989), Gurjar and Thierauf (2020)]. We show that this class is closed under approximation. In the language of algebraic geometry, we show that the set obtained by taking coordinatewise products of pairs of points from (the Plücker embedding of) a Grassmannian variety is closed.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Hadamard products of hypersurfacesJournal of Pure and Applied Algebra, 2022
- Linear Matroid Intersection is in Quasi-NCcomputational complexity, 2020
- On Algebraic Branching Programs of Small WidthJournal of the ACM, 2018
- Polynomial relations among principal minors of a -matrixJournal of Algebra, 2009
- Valuated Matroid Intersection I: Optimality CriteriaSIAM Journal on Discrete Mathematics, 1996
- Valuated matroids: a new look at the greedy algorithmApplied Mathematics Letters, 1990
- Singular spaces of matrices and their application in combinatoricsBulletin of the Brazilian Mathematical Society, New Series, 1989
- A weighted matroid intersection algorithmJournal of Algorithms, 1981
- Systems of distinct representatives and linear algebraJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967
- Transversals and Matroid Partition1965