Prerona Chatterjee

@niser.ac.in

Assistant Professor, School of Computer Sciences
National Institiute of Science Education and Research

Prerona Chatterjee


                     Download Compact PDF  
https://researchid.co/preronac

RESEARCH, TEACHING, or OTHER INTERESTS

Computational Theory and Mathematics
13

Scopus Publications

65

Scholar Citations

4

Scholar h-index

2

Scholar i10-index

Scopus Publications

  • IPS lower bounds for formulas and sum of ROABPs
    Chatterjee, Prerona, Ghosal, Utsab, Mukhopadhyay, Partha, Sinhababu, Amit
    Leibniz International Proceedings in Informatics Lipics, 2025
    We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi [Joshua A. Grochow and Toniann Pitassi, 2018]. The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation [Paul Beame et al., 1994] and simulates Extended Frege efficiently. Our main results are as follows. - mult-IPS_{Lin'}: We prove nearly quadratic-size formula lower bound for multilinear refutation (over the Boolean hypercube) of a variant of the subset-sum axiom polynomial. Extending this, we obtain a nearly matching qualitative statement for a constant degree target polynomial. - IPS_{Lin'}: Over the fields of characteristic zero, we prove exponential-size sum-of-ROABPs lower bound for the refutation of a variant of the subset-sum axiom polynomial. The result also extends over the fields of positive characteristics when the target polynomial is suitably modified. The modification is inspired by the recent results [Tuomas Hakoniemi et al., 2024; Amik Raj Behera et al., 2025]. The mult-IPS_{Lin'} lower bound result is obtained by combining the quadratic-size formula lower bound technique of Kalorkoti [Kalorkoti, 1985] with some additional ideas. The proof technique of IPS_{Lin'} lower bound result is inspired by the recent lower bound result of Chatterjee, Kush, Saraf and Shpilka [Prerona Chatterjee et al., 2024].
  • Monotone classes beyond VNP
    Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
    Theoretical Computer Science, 2024
  • Lower Bounds for Set-Multilinear Branching Programs
    Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
    Leibniz International Proceedings in Informatics Lipics, 2024
    In this paper, we prove super-polynomial lower bounds for the model of sum of ordered set-multilinear algebraic branching programs, each with a possibly different ordering (∑smABP). Specifically, we give an explicit nd-variate polynomial of degree d such that any ∑smABP computing it must have size n^ω(1) for d as low as ω(log n). Notably, this constitutes the first such lower bound in the low degree regime. Moreover, for d = poly(n), we demonstrate an exponential lower bound. This result generalizes the seminal work of Nisan (STOC, 1991), which proved an exponential lower bound for a single ordered set-multilinear ABP. The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (TAMC, 2024), which showed that super-polynomial lower bounds against a sum of ordered set-multilinear branching programs - for a polynomial of sufficiently low degree - would imply super-polynomial lower bounds against general ABPs, thereby resolving Valiant’s longstanding conjecture that the permanent polynomial can not be computed efficiently by ABPs. More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by O(log n/ log log n), then it would imply super-polynomial lower bounds against general ABPs. Our results strengthen the works of Arvind & Raja (Chic. J. Theor. Comput. Sci., 2016) and Bhargav, Dwivedi & Saxena (TAMC, 2024), as well as the works of Ramya & Rao (Theor. Comput. Sci., 2020) and Ghoshal & Rao (International Computer Science Symposium in Russia, 2021), each of which established lower bounds for related or restricted versions of this model. They also strongly answer a question from the former two, which asked to prove super-polynomial lower bounds for general ∑smABP.
  • Monotone Classes Beyond VNP
    Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
    Leibniz International Proceedings in Informatics Lipics, 2023
    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 of large sparsity are hard for the monotone analogues of all the known definitions of VPSPACE, except for the one due to Poizat.
  • New Lower Bounds Against Homogeneous Non-Commutative Circuits
    Prerona Chatterjee, Pavel Hrubeš
    Leibniz International Proceedings in Informatics Lipics, 2023
    We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $Ω(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $Ω(nd)$, if $d\leq n$, or $Ω(nd \frac{\log n}{\log d})$, if $d\geq n$. Under the same assumptions, we also give a quadratic lower bound for the ordered version of the central symmetric polynomial.
  • Constructing Faithful Homomorphisms over Fields of Finite Characteristic
    Prerona Chatterjee, Ramprasad Saptharishi
    ACM Transactions on Computation Theory, 2023
    We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken et al. [ 3 ] and exploited by them, and Agrawal et al. [ 2 ] to design algebraic independence–based identity tests using the Jacobian criterion over characteristic zero fields. An analogue of such constructions over finite characteristic fields was unknown due to the failure of the Jacobian criterion over finite characteristic fields. Building on a recent criterion of Pandey et al. [ 15 ], we construct explicit faithful maps for some natural classes of polynomials in the positive characteristic field setting, when a certain parameter called the inseparable degree of the underlying polynomials is bounded (this parameter is always 1 in fields of characteristic zero). This presents the first generalisation of some of the results of Beecken et al. [ 3 ] and Agrawal et al. [ 2 ] in the positive characteristic setting.
  • Quadratic Lower Bounds for Algebraic Branching Programs and Formulas
    Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk
    Computational Complexity, 2022
  • Separating ABPs and some structured formulas in the non-commutative setting
    Prerona Chatterjee
    Leibniz International Proceedings in Informatics Lipics, 2021
    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, we generalise the notion of ordered polynomials in the non-commutative setting (defined by \Hrubes, Wigderson and Yehudayoff (2011)) to define abecedarian polynomials and models that naturally compute them. Our main contribution is a possible new approach towards separating formulas and ABPs in the non-commutative setting, via lower bounds against abecedarian formulas. In particular, we show the following. There is an explicit n-variate degree d abecedarian polynomial $f_{n,d}(x)$ such that 1. $f_{n, d}(x)$ can be computed by an abecedarian ABP of size O(nd); 2. any abecedarian formula computing $f_{n, \log n}(x)$ must have size that is super-polynomial in n. We also show that a super-polynomial lower bound against abecedarian formulas for $f_{\log n, n}(x)$ would separate the powers of formulas and ABPs in the non-commutative setting.
  • Generalized Parametric Path Problems
    37th Conference on Uncertainty in Artificial Intelligence Uai 2021, 2021
  • Generalized Parametric Path Problems
    Proceedings of Machine Learning Research, 2021
  • On the existence of algebraically natural proofs
    Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse
    Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs, 2020
  • A quadratic lower bound for algebraic branching programs
    Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk
    Leibniz International Proceedings in Informatics Lipics, 2020
  • Constructing faithful homomorphisms over fields of finite characteristic
    Prerona Chatterjee, Ramprasad Saptharishi
    Leibniz International Proceedings in Informatics Lipics, 2019

RECENT SCHOLAR PUBLICATIONS

  • IPS Lower Bounds for Formulas and Sum of ROABPs
    P Chatterjee, U Ghosal, P Mukhopadhyay, A Sinhababu
    arXiv preprint arXiv:2507.09515 , 2025
    2025
    Citations: 3
  • Monotone classes beyond VNP
    P Chatterjee, K Gajjar, A Tengse
    Theoretical Computer Science 1009, 114689 , 2024
    2024
    Citations: 1
  • Lower Bounds for Set-Multilinear Branching Programs
    P Chatterjee, D Kush, S Saraf, A Shpilka
    39th Computational Complexity Conference (CCC 2024), 20: 1-20: 20 , 2024
    2024
    Citations: 5
  • Lower Bounds from Succinct Hitting Sets
    P Chatterjee, A Tengse
    arXiv e-prints, arXiv: 2309.07612 , 2023
    2023
    Citations: 1
  • Constructing Faithful Homomorphisms over Fields of Finite Characteristic
    P Chatterjee, R Saptharishi
    ACM Transactions on Computation Theory 15 (1-2), 1-19 , 2023
    2023
    Citations: 4
  • New Lower Bounds against Homogeneous Non-Commutative Circuits
    P Chatterjee, P Hrubeš
    arXiv preprint arXiv:2301.01676 , 2023
    2023
    Citations: 4
  • Quadratic Lower Bounds for Algebraic Branching Programs and Formulas
    P Chatterjee, M Kumar, A She, B Lee Volk
    computational complexity 31 (2), 1-54 , 2022
    2022
    Citations: 27
  • Generalized parametric path problems
    K Gajjar, G Varma, P Chatterjee, J Radhakrishnan
    Uncertainty in Artificial Intelligence, 536-546 , 2021
    2021
  • Separating ABPs and some structured formulas in the non-commutative setting
    P Chatterjee
    arXiv preprint arXiv:2103.00864 , 2021
    2021
    Citations: 6
  • On the existence of algebraically natural proofs
    P Chatterjee, M Kumar, C Ramya, R Saptharishi, A Tengse
    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS … , 2020
    2020
    Citations: 14

MOST CITED SCHOLAR PUBLICATIONS

  • Quadratic Lower Bounds for Algebraic Branching Programs and Formulas
    P Chatterjee, M Kumar, A She, B Lee Volk
    computational complexity 31 (2), 1-54 , 2022
    2022
    Citations: 27
  • On the existence of algebraically natural proofs
    P Chatterjee, M Kumar, C Ramya, R Saptharishi, A Tengse
    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS … , 2020
    2020
    Citations: 14
  • Separating ABPs and some structured formulas in the non-commutative setting
    P Chatterjee
    arXiv preprint arXiv:2103.00864 , 2021
    2021
    Citations: 6
  • Lower Bounds for Set-Multilinear Branching Programs
    P Chatterjee, D Kush, S Saraf, A Shpilka
    39th Computational Complexity Conference (CCC 2024), 20: 1-20: 20 , 2024
    2024
    Citations: 5
  • Constructing Faithful Homomorphisms over Fields of Finite Characteristic
    P Chatterjee, R Saptharishi
    ACM Transactions on Computation Theory 15 (1-2), 1-19 , 2023
    2023
    Citations: 4
  • New Lower Bounds against Homogeneous Non-Commutative Circuits
    P Chatterjee, P Hrubeš
    arXiv preprint arXiv:2301.01676 , 2023
    2023
    Citations: 4
  • IPS Lower Bounds for Formulas and Sum of ROABPs
    P Chatterjee, U Ghosal, P Mukhopadhyay, A Sinhababu
    arXiv preprint arXiv:2507.09515 , 2025
    2025
    Citations: 3
  • Monotone classes beyond VNP
    P Chatterjee, K Gajjar, A Tengse
    Theoretical Computer Science 1009, 114689 , 2024
    2024
    Citations: 1
  • Lower Bounds from Succinct Hitting Sets
    P Chatterjee, A Tengse
    arXiv e-prints, arXiv: 2309.07612 , 2023
    2023
    Citations: 1
  • Generalized parametric path problems
    K Gajjar, G Varma, P Chatterjee, J Radhakrishnan
    Uncertainty in Artificial Intelligence, 536-546 , 2021
    2021