Publications
-
Derandomization from Algebraic Hardness (borderless)
- With Zeyu Guo, Mrinal Kumar, Noam Solomon
- Slides
- An earlier version of this is due to appear in FOCS 2019.
-
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
- With Mrinal Kumar, Rafael Oliveira
- To appear in 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
- Ph.D. 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