Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PRERONA CHATTERJEE:
All reports by Author Prerona Chatterjee:

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

On the Existence of Algebraically Natural Proofs

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


TR19-170 | 27th November 2019
Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

A Quadratic Lower Bound for Algebraic Branching Programs

Revisions: 3

We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves upon the lower bound of $\Omega(n\log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results by Kumar [Kum19], which showed ... more >>>


TR18-212 | 26th December 2018
Prerona Chatterjee, Ramprasad Saptharishi

Constructing Faithful Homomorphisms over Fields of Finite Characteristic

We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests ... more >>>




ISSN 1433-8092 | Imprint