Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VALUATED MATROID:
Reports tagged with Valuated Matroid:
TR23-075 | 17th May 2023
Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj

Border Complexity of Symbolic Determinant under Rank One Restriction

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 ... more >>>




ISSN 1433-8092 | Imprint