11 citations · 17 across the 4 of their papers we have counts for
6 papers · 1 filter
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…
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
Mrinal Kumar, Rafael Oliveira, Ramprasad Saptharishi
We show that any -variate polynomial computable by a syntactically multilinear circuit of size can be computed by a depth- syntactically multilinear…