Research

Papers

• Lower Bounds from Succinct Hitting Sets [CT],
  • with Prerona Chatterjee.
  • Manuscript.
• The Complexity of Order-Finding for ROABPs [BDGT],
  • with Vishwas Bhargava, Pranjal Dutta and Sumanta Ghosh.
  • Manuscript.
• Explicit Commutative ROABPs from Partial Derivatives [BT24],
  • with Vishwas Bhargava.
  • Conference version appeared in the proceedings of FSTTCS 2024.
• On Existence of Algebraic Natural Proofs,
  • with Prerona Chatterjee, Mrinal Kumar, C. Ramya and Ramprasad Saptharishi.
  • Full version of [CKRST20] and [KRST22], under review for a journal.
• Monotone Classes Beyond VNP [CGT23],
  • with Prerona Chatterjee and Kshitij Gajjar (dblp).
  • Full version published in Theoretical Computer Science, September 2024.
  • Conference version appeared in the proceedings of FSTTCS 2023.
• On Finer Separations between Subclasses of Read-once Oblivious ABPs [RT22],
  • with C. Ramya.
  • Conference version appeared in the proceedings of STACS 2022.
• If VNP is hard, then so are Equations for it [KRST22],
  • with Mrinal Kumar, C. Ramya and Ramprasad Saptharishi.
  • Conference version appeared in the proceedings of STACS 2022.
• On Existence of Algebraic Natural Proofs [CKRST20],
  • with Prerona Chatterjee, Mrinal Kumar, C. Ramya and Ramprasad Saptharishi.
  • Preliminary Version appeared in the proceedings of FOCS 2020.
• Near-optimal Bootstrapping Hitting Sets for Algebraic Models [KST23],
  • with Mrinal Kumar and Ramprasad Saptharishi.
  • Full version published in Theory of Computing, December 2023.
  • Preliminary version appeared in the proceedings of SODA 2019.
• Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees [ST18],
  • with Ramprasad Saptharishi.
  • Appeared in the proceedings of FSTTCS 2018.

Reports and expositions

• Hitting Sets for Algebraic Models: Constructions and Consequences,
  • PhD thesis, advised by Ramprasad Saptharishi.
• Contributed Chapter 15 in the A selection of lower bounds in arithmetic circuit complexity
  • Modified version of the exposition prepared as a part of a course taught by Ramprasad Saptharishi