1 citations · 1 across the 7 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.CC2020
If VNP is hard, then so are equations for it
Mrinal Kumar, C. Ramya, Ramprasad Saptharishi +1
Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, a…
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.CC2020
On the Existence of Algebraic Natural Proofs
Prerona Chatterjee, Mrinal Kumar, C Ramya +2
The framework of algebraically natural proofs was independently introduced in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), to study the…