11 citations · 17 across the 3 of their papers we have counts for
13 papers · 1 filter
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…
Schur Polynomials do not have small formulas if the Determinant doesn't!
Prasad Chaugule, Mrinal Kumar, Nutan Limaye +3
Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric fu…
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)…
Derandomization from Algebraic Hardness
Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi +1
A hitting-set generator (HSG) is a polynomial map such that for all -variate polynomials of small enough circuit size and degree, if is…
Closure of VP under taking factors: a short and simple proof
Chi-Ning Chou, Mrinal Kumar, Noam Solomon
In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an variate degree $…
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…