Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MRINAL KUMAR:
All reports by Author Mrinal Kumar:

TR23-115 | 8th August 2023
Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

Determinants vs. Algebraic Branching Programs

Revisions: 1

We show that for every homogeneous polynomial of degree $d$, if it has determinantal complexity at most $s$, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most $O(d^5s)$. Moreover, we show that for \textit{most} homogeneous polynomials, the width of the resulting homogeneous ABP ... more >>>


TR21-163 | 19th November 2021
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar

Algorithmizing the Multiplicity Schwartz-Zippel Lemma

Revisions: 1

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found nu- merous applications in both math and computer ... more >>>


TR20-187 | 13th December 2020
Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

If VNP is hard, then so are equations for it

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 >>>


TR20-063 | 29th April 2020
Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

On the Existence of Algebraically Natural Proofs

Revisions: 2

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 >>>




ISSN 1433-8092 | Imprint