4 papers
A Polynomial Degree Bound on Equations of Non-rigid Matrices and Small Linear Circuits
Mrinal Kumar, Ben Lee Volk
We show that there is a defining equation of degree at most for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large…
A Quadratic Lower Bound for Algebraic Branching Programs and Formulas
Prerona Chatterjee, Mrinal Kumar, Adrian She +1
We show that any Algebraic Branching Program (ABP) computing the polynomial has at least vertices. This improves upon the lower bound of $Ω(n\log n)…
Lower Bounds for Matrix Factorization
Mrinal Kumar, Ben Lee Volk
We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical ques…
Pseudorandom Bits for Oblivious Branching Programs
Rohit Gurjar, Ben Lee Volk
We construct a pseudorandom generator which fools read- oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequen…