Abstract
VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where the size of each A_i is polynomial in the number of variables (equivalently, computable by polynomialsized algebraic branching programs (ABP)). A major open problem in geometric complexity theory (GCT) is to determine whether VBP is closed under approximation i.e. whether VBP = VBP^ ̅. The power of approximation is well understood for some restricted models of computation, e.g. the class of depthtwo circuits, readonce oblivious ABPs (ROABP), monotone ABPs, depththree circuits of bounded top fanin, and widthtwo ABPs. The former three classes are known to be closed under approximation [Markus Bläser et al., 2020], whereas the approximative closure of the last one captures the entire class of polynomial families computable by polynomialsized formulas [Bringmann et al., 2017].
In this work, we consider the subclass of VBP computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where for each 1 ≤ i ≤ n, A_i is of rank one. This class has been studied extensively [Edmonds, 1968; Jack Edmonds, 1979; Murota, 1993] and efficient identity testing algorithms are known for it [Lovász, 1989; Rohit Gurjar and Thomas 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.
BibTeX  Entry
@InProceedings{chatterjee_et_al:LIPIcs.CCC.2023.2,
author = {Chatterjee, Abhranil and Ghosh, Sumanta and Gurjar, Rohit and Raj, Roshan},
title = {{Border Complexity of Symbolic Determinant Under Rank One Restriction}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {2:12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772822},
ISSN = {18688969},
year = {2023},
volume = {264},
editor = {TaShma, Amnon},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18272},
URN = {urn:nbn:de:0030drops182721},
doi = {10.4230/LIPIcs.CCC.2023.2},
annote = {Keywords: Border Complexity, Symbolic Determinant, Valuated Matroid}
}
Keywords: 

Border Complexity, Symbolic Determinant, Valuated Matroid 
Collection: 

38th Computational Complexity Conference (CCC 2023) 
Issue Date: 

2023 
Date of publication: 

10.07.2023 