Author name cluster

Prerona Chatterjee

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

TCS Journal 2024 Journal Article

Monotone classes beyond VNP

Prerona Chatterjee
Kshitij Gajjar
Anamay Tengse

In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than VNP. We observe that these monotone analogues are not equivalent unlike their non-monotone counterparts, and propose monotone VPSPACE ( mVPSPACE ) to be defined as the monotone analogue of Poizat's definition. With this definition, mVPSPACE turns out to be exponentially stronger than mVNP and also satisfies several desirable closure properties that the other analogues may not. Our initial goal was to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš & Yehudayoff (2021). In that context, we show that transparent polynomials with large support are hard for the monotone analogues of all the known definitions of VPSPACE, except for the one due to Poizat.

Details DOI

UAI Conference 2021 Conference Paper

Generalized parametric path problems

Kshitij Gajjar
Girish Varma
Prerona Chatterjee
Jaikumar Radhakrishnan

Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation is applicable in these domains. We study the complexity of the general problem, and a variant of it where preprocessing is allowed. We show that when the parametric weights are linear functions, algorithms remain tractable even under our relaxed assumptions. Furthermore, we show that if the weights are allowed to be non-linear, the problem becomes NP-hard. We also study the multi-dimensional version of the problem where the weight functions are parameterized by multiple parameters. We show that even with two parameters, this problem is NP-hard.

Details

FOCS Conference 2020 Conference Paper

On the Existence of Algebraically Natural Proofs

Prerona Chatterjee
Mrinal Kumar 0001
C. Ramya
Ramprasad Saptharishi
Anamay Tengse

For every constant, we show that there is a family {PN, c} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, that satisfies the following properties: For every family {fn} of polynomials in VP, where fn is an n variate polynomial of degree at most n c with bounded integer coefficients and for N=n c +nn, PN, c vanishes on the coefficient vector of fn. There exists a family {hn} of polynomials where hn is an n variate polynomial of degree at most n c with bounded integer coefficients such that for N=n c +nn, PN, c does not vanish on the coefficient vector of hn. In other words, there are efficiently computable equations for polynomials in VP that have small integer coefficients. In fact, we also prove an analogous statement for the seemingly larger class VNP. Thus, in this setting of polynomials with small integer coefficients, this provides evidence against a natural proof like barrier for proving algebraic circuit lower bounds, a framework for which was proposed in the works of Forbes, Shpilka and Volk [1], and Grochow, Kumar, Saks and Saraf [2]. Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes and also extend to finite fields of small size. Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes and also extend to finite fields of small size.

Details