Publications
This page includes both research papers / manuscripts, and also some expositions.
Papers
- Constant-depth circuits for polynomial GCD over any characteristic
- Closure under factorization from a result of Furstenberg
-
Deterministic factorization of constant-depth algebraic circuits in subexponential time
- With Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Shubhangi Saraf
- Under submission
-
An exposition of recent list-size bounds of FRS Codes
- With Abhibhav Garg, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar
- Exposition
-
An Improved Line-Point Low-Degree Test
- With Prahladh Harsha, Mrinal Kumar, Madhu Sudan
- FOCS 2024
-
Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
- With Mrinal Kumar, Varun Ramanathan, Ben Lee Volk
- Under submission
-
Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits
- With Mrinal Kumar, Varun Ramanathan
- SODA 2024
-
Fast Numerical Multivariate Multipoint Evaluation
- With Sumanta Ghosh, Prahladh Harsha, Simão Herdade, Mrinal Kumar
- FOCS 2023
-
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
- With Siddharth Bhandari, Prahladh Harsha, Srikanth Srinivasan
- To appear in CCC 2022
-
If VNP is hard, then so are equations for it
- With Mrinal Kumar, C Ramya, Anamay Tengse
- STACS 2022
-
COVID-19 Epidemic in Mumbai: Projections, full economic opening, and containment zones versus contact tracing and testing: An Update
- With Prahladh Harsha, Sandeep Juneja, Daksh Mittal
- [2021-04-13] We failed to predict the second wave (A general article introspecting modelling efforts.)
-
City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic
- With Shubhada Agrawal, Siddharth Bhandari, Anirban Bhattacharjee, Anand Deo, Narendra M Dixit, Prahladh Harsha, Sandeep Juneja, Poonam Kesarwani, Aditya Krishna Swamy, Preetam Patil, Nihesh Rathod, Sharad Sriram, Piyush Srivastava, Rajesh Sundaresan, Nidhin Koshy Vaidhiyan, A Y Sarath
- Manuscript. Code available at github.
-
COVID-19 Epidemic Study II: Phased Emergence from the Lockdown in Mumbai
- With Prahladh Harsha, Sandeep Juneja, Preetam Patil, Nihesh Rathod, Sharad Sriram, Piyush Srivastava, Rajesh Sundaresan, Nidhin Koshy Vaidhiyan, A Y Sarath
- Manuscript. Code available at github.
-
On the Existence of Algebraically Natural Proofs
- With Prerona Chatterjee, Mrinal Kumar, C Ramya, Anamay Tengse
- To appear in FOCS 2020
-
A note on the elementary HDX construction of Kaufman-Oppenheim
- With Prahladh Harsha
- Manuscript
-
Derandomization from Algebraic Hardness (borderless)
- With Zeyu Guo, Mrinal Kumar, Noam Solomon
- Slides
- An earlier version of this appeared in FOCS 2019.
-
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
- With Mrinal Kumar, Rafael Oliveira
- ICALP 2019
-
Constructing Faithful Homomorphisms over Fields of Finite Characteristic
- With Prerona Chatterjee
- FSTTCS 2019
-
Near-optimal Bootstrapping of Hitting Sets for Algebraic Models
- With Mrinal Kumar, Anamay Tengse
- Slides
- An earlier version appeared in SODA 2019
-
Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees
- With Anamay Tengse
- To appear in FSTTCS 2018
- Finer separations between shallow arithmetic circuits
-
An exponential lower bound for homogeneous depth-5 circuits over finite fields
- With Mrinal Kumar
- CCC 2017
- Slides
- Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
- Identity testing and lower bounds for read-k oblivious algebraic branching programs
- Efficiently decoding Reed-Muller codes from random errors
-
The Chasm at Depth Four, and Tensor Rank : Old results, new insights
- With Suryajith Chillara, Mrinal Kumar, V Vinay
- Manuscript
-
On Fortification of Projection Games
- With Amey Bhangale, Girish Varma, Rakesh Venkat
- RANDOM 2015
-
(Github survey) A selection of lower bounds in arithmetic circuit complexity
- Looking for contributors
- Recent Progress on Arithmetic Circuit Lower Bounds
-
A selection of lower bounds for arithmetic circuits
- With Neeraj Kayal
- Perspectives in Complexity Theory 2014
- Special issue in the event of Somenath Biswas' 60th Birthday.
- Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
- A super-polynomial lower bound for regular arithmetic formulas
-
Unified Approaches to Polynomial Identity Testing and Lower Bounds
- PhD Thesis (2013)
- Won the ACM (India) Doctoral Dissertation Award 2013
- Arithmetic circuits: A chasm at depth three
- Approaching the chasm at depth four
- Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits
- A Case of Depth-3 Identity Testing, Sparse Factorization and Duality
-
Classifying polynomials and identity testing
- With Manindra Agrawal
- Current Trends in Science 2009
- Survey
-
Arithmetic Circuits and Identity Testing
- M.Sc. Thesis (2009)
- The Power of Depth 2 Circuits over Algebras
- Fast Integer Multiplication Using Modular Computation
Expositions
These were exposition mostly written for my own benefit. They haven’t been carefully proofread. If you notice any bugs, please let me know and I’ll be happy to update it.