All reports by Author Mrinal Kumar:

__
TR20-187
| 13th December 2020
__

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### If VNP is hard, then so are equations for it

__
TR20-063
| 29th April 2020
__

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### On the Existence of Algebraically Natural Proofs

Revisions: 1

Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

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, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size.

In a ... more >>>

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:

* For every family {f_n} of polynomials in VP, where f_n is an n ...
more >>>