All reports by Author Prerona Chatterjee:

__
TR22-031
| 16th February 2022
__

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse#### Transparency Beyond VNP in the Monotone Setting

__
TR21-037
| 1st March 2021
__

Prerona Chatterjee#### Separating ABPs and Some Structured Formulas in the Non-Commutative Setting

__
TR20-063
| 29th April 2020
__

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

Revisions: 1

__
TR19-170
| 27th November 2019
__

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk#### A Quadratic Lower Bound for Algebraic Branching Programs

Revisions: 3

__
TR18-212
| 26th December 2018
__

Prerona Chatterjee, Ramprasad Saptharishi#### Constructing Faithful Homomorphisms over Fields of Finite Characteristic

Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

Recently Hrubes and Yehudayoff (2021) showed a connection between the monotone algebraic circuit complexity of \emph{transparent} polynomials and a geometric complexity measure of their Newton polytope. They then used this connection to prove lower bounds against monotone VP (mVP). We extend their work by showing that their technique can be ... more >>>

Prerona Chatterjee

The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question continues to remain open, we make some progress towards its resolution. To that effect, ... 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 >>>

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

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

Prerona Chatterjee, Ramprasad Saptharishi

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