Articles
- Testing equivalence to design polynomials
with Omkar Baraskar and Agrim Dewan.
41st International Symposium on Theoretical Aspects of Computer Science (STACS), 2024
- Low-depth arithmetic circuit lower bounds: Bypassing set-multilinearization
with Prashanth Amireddy, Ankit Garg, Neeraj Kayal and Bhargav Thankey.
50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023
- Equivalence test for read-once arithmetic formulas
with Nikhil Gupta and Bhargav Thankey.
34th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023
- Learning generalized depth three arithmetic circuits in the non-degenerate case
with Vishwas Bhargava, Ankit Garg and Neeraj Kayal.
26th International Conference on Randomization and Computation (RANDOM), 2022
- Hitting sets for orbits of circuit classes and polynomial families
with Bhargav Thankey.
25th International Conference on Randomization and Computation (RANDOM), 2021
- Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests
with Janaky Murthy and Vineet Nair.
45th Symposium on Mathematical Foundations of Computer Science (MFCS), 2020
- A super-quadratic lower bound for depth four arithmetic circuits
with Nikhil Gupta and Bhargav Thankey.
35th Computational Complexity Conference (CCC), 2020
- Learning sums of powers of low-degree polynomials in the non-degenerate case
with Ankit Garg and Neeraj Kayal.
61st IEEE Symposium on Foundations of Computer Science (FOCS), 2020
- Determinant equivalence test over finite fields and over Q
with Ankit Garg, Nikhil Gupta and Neeraj Kayal.
46th International Colloquium on Automata, Languages and Programming (ICALP), 2019
- Reconstruction of non-degenerate homogeneous depth three circuits
with Neeraj Kayal.
51st ACM Symposium on Theory of Computing (STOC), 2019
- On the symmetries of and equivalence test for design polynomials
with Nikhil Gupta.
44th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2019
- Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs
with Neeraj Kayal and Vineet Nair.
Computational Complexity (CC), volume 28(4), 2019
- A Paradigm for Arithmetic Circuit Lower Bounds
with Neeraj Kayal.
ACM SIGACT News, volume 49(1), 2018
- Improved lower bound for multi-r-ic depth four circuits as a function of the number of input variables
with Sumant Hegde.
Proceedings of Indian National Science Academy (PINSA), volume 83(4), 2017
- Reconstruction of full rank Algebraic Branching Programs
with Neeraj Kayal, Vineet Nair and Sébastien Tavenas.
Invited to ACM Transactions on Computation Theory (ToCT) journal, volume 11(1), 2018
32nd IEEE Conference on Computational Complexity (CCC), 2017
- An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
with Neeraj Kayal and Sébastien Tavenas.
43rd International Colloquium on Automata, Languages, and Programming (ICALP), 2016
(Best Paper Award)
- On the size of homogeneous and of depth four formulas with low individual degree
with Neeraj Kayal and Sébastien Tavenas.
Invited to Theory of Computing (ToC) journal, volume 14(16), 2018
48th ACM Symposium on Theory of Computing (STOC), 2016
- Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
with Neeraj Kayal and Vineet Nair.
Invited to ACM Transactions on Computation Theory (ToCT) journal
33rd Symposium on Theoretical Aspects of Computer Science (STACS), 2016
- Lower Bounds for sums of powers of low degree univariates
with Neeraj Kayal, Pascal Koiran and Timothée Pecatte.
42nd International Colloquium on Automata, Languages, and Programming (ICALP), 2015
- Multi-k-ic depth three circuit lower bound
with Neeraj Kayal.
Invited to a special issue of Theory of Computing Systems (ToCS), volume 61(4), 2017
32nd Symposium on Theoretical Aspects of Computer Science (STACS), 2015
- Lower bound for sums of products of low arity polynomials
with Neeraj Kayal.
Electronic Colloquium on Computational Complexity (ECCC), TR15-073, 2015
- Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin
with Neeraj Kayal.
Invited to the special issue of Computational Complexity (CC), volume 25(2), 2016
30th IEEE Conference on Computational Complexity (CCC), 2015
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
with Neeraj Kayal, Nutan Limaye and Srikanth Srinivasan.
Invited to a special issue of SIAM Journal of Computing (SICOMP), volume 46(1), 2017
55th IEEE Symposium on Foundations of Computer Science (FOCS), 2014
- Super-polynomial Lower Bounds for Depth Four Homogeneous Arithmetic Formulas
with Neeraj Kayal, Nutan Limaye and Srikanth Srinivasan.
46th ACM Symposium on Theory of Computing (STOC), 2014
- A super-polynomial lower bound for regular arithmetic formulas
with Neeraj Kayal and Ramprasad Saptharishi.
46th ACM Symposium on Theory of Computing (STOC), 2014
- Quasi-polynomial hitting-set for set-depth-D formulas
with Manindra Agrawal and Nitin Saxena.
45th ACM Symposium on Theory of Computing (STOC), 2013
- Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits
with Manindra Agrawal, Ramprasad Saptharishi and Nitin Saxena.
Invited to the special issue of SIAM Journal of Computing (SICOMP), volume 45(4), 2016
44th ACM Symposium on Theory of Computing (STOC), 2012
- A Case of Depth-3 Identity Testing, Sparse Factorization and Duality
with Ramprasad Saptharishi and Nitin Saxena.
Computational Complexity (CC), volume 22(1), 2013
- On the Sum of Square Roots of Polynomials and related problems
with Neeraj Kayal.
Invited to ACM Transactions on Computation Theory (ToCT), volume 4(4), 2012
26th IEEE Conference on Computational Complexity (CCC), 2011
- The Power of Depth 2 Circuits over Algebras
with Ramprasad Saptharishi and Nitin Saxena.
29th Foundation of Software Technology and Theoretical Computer Science (FSTTCS), 2009
- Covering a Set of Points in a Plane using Two Parallel Rectangles,
with Sandip Das.
Information Processing Letters (IPL), volume 109(16), 2009
- Fast Integer Multiplication Using Modular Arithmetic
with Anindya De, Piyush Kurur and Ramprasad Saptharishi.
SIAM Journal of Computing (SICOMP), volume 42(2), 2013
40th Annual ACM Symposium on Theory of Computing (STOC), 2008
- Factoring Polynomials over Finite Fields using Balance Test
25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2008.
- Simpler algorithm for estimating frequency moments of data streams,
with Lakshminath Bhuvanagiri, Sumit Ganguly and Deepanjan Kesh.
17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.
- Practical Algorithms for Tracking Database Join Sizes,
with Sumit Ganguly and Deepanjan Kesh.
25th Foundation of Software Technology and Theoretical Computer Science (FSTTCS), 2005.
(Unpublished) articles