3 papers
cs.CC2020
Recent Progress on Matrix Rigidity -- A Survey
C. Ramya
The concept of matrix rigidity was introduced by Valiant(independently by Grigoriev) in the context of computing linear transformations. A matrix is rigid if it is far(in terms of…
cs.CC2019
Lower bounds for multilinear bounded order ABPs
C. Ramya, B. V. Raghavendra Rao
Proving super-polynomial size lower bounds for syntactic multilinear Algebraic Branching Programs(smABPs) computing an explicit polynomial is a challenging problem in Algebraic Com…
cs.CC2018
Lower Bounds for Special Cases of Syntactic Multilinear ABPs
C. Ramya, B. V. Raghavendra Rao
Algebraic Branching Programs(ABPs) are standard models for computing polynomials. Syntactic multilinear ABPs (smABPs) are restrictions of ABPs where every variable is allowed to oc…