11 citations · 15 across the 2 of their papers we have counts for
3 papers
cs.CC2019★ 4 cited
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 $…
cs.CC2016
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi
We say that a circuit over a field functionally computes an -variate polynomial if for every we have that . This is in contrast to syn…
cs.CC2015★ 11 cited
An exponential lower bound for homogeneous depth-5 circuits over finite fields
Mrinal Kumar, Ramprasad Saptharishi
In this paper, we show exponential lower bounds for the class of homogeneous depth- circuits over all small finite fields. More formally, we show that there is an explicit famil…