Papers :
-
High rate multivariate polynomial evaluation codes
with Swastik Kopparty and Harry Sha
-
Towards detertministic algorithms for constant depth factors of constant depth circuits
with Varun Ramanathan, Ramprasad Saptharishi and Ben Lee Volk
-
Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
with Rohan Goyal, Prahladh Harsha and Ashutosh Shankar
-
An improved line-point low degree test
with Prahladh Harsha, Ramprasad Saptharishi and Madhu Sudan
-
Detertministic algorithms for low degree factors of constant depth circuits
with Varun Ramanathan and Ramprasad Saptharishi
-
Determinants vs algebraic branching programs
with Abhranil Chatterjee and Ben Lee Volk
-
Fast numerical multivariate multipoint evaluation
with Prahladh Harsha, Sumanta Ghosh, Simao Herdade and Ramprasad Saptharishi
-
Fast multivariate multipoint evaluation over all finite fields
with Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo and Chris Umans
-
Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
with Vishwas Bhargava, Sumanta Ghosh and Chandra Kant Mohapatra
-
Algorithmizing the multiplicity Schwartz-Zippel lemma
with Siddharth Bhandari, Prahladh Harsha and A Shankar
-
Ideal-theoretic explanation of capacity-achieving decoding
with Siddharth Bhandari, Prahladh Harsha and Madhu Sudan
- If VNP is hard, then so are equations for it
with C Ramya, Ramprasad Saptharishi and Anamay Tengse
- Decoding multivariate multiplicity codes on product sets
with Siddharth Bhandari, Prahladh Harsha and Madhu Sudan
- A lower bound on determinantal complexity
with Ben Lee Volk
- On the existence of algebraically natural proofs
with Prerona Chatterjee, C Ramya, Ramprasad Saptharishi and Anamay Tengse
- A polynomial degree bound on equations of non-rigid matrces and small linear circuits
with Ben Lee Volk
- Monotone circuit lower bounds from robust sunflowers
with Bruno Pasqualotto Cavalar and Benjamin Rossman
- A quadratic lower bound for algebraic branching programs and formulas
with Prerona Chatterjee, Adrian She and Ben Lee Volk
Subsumes the results in an earlier version of this paper.
- Schur polynomials do not have small formulas if the determinant doesn't!
with Prasad Chaugule, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She and Srikanth Srinivasan
- Hardness randomness tradeoffs for algebraic computation (a survey)
with Ramprasad Saptharishi
- Derandomization from algebraic hardness: Treading the borders
with Zeyu Guo, Ramprasad Saptharishi and Noam Solomon
Subsumes and improves upon some of the results in an earlier version with Ramprasad Saptharishi and Noam Solomon.
- Lower bounds for matrix factorization
with Ben Lee Volk
- Closure of VP under taking factors: a short and simple proof
with Chi-Ning Chou and Noam Solomon
- Towards optimal depth reductions for syntactically multilinear circuits
with Rafael Oliveira and Ramprasad Saptharishi
- Near optimal bootstrapping for hitting sets for algebraic models
with Ramprasad Saptharishi and Anamay Tengse
- On multilinear forms : bias, correlation, and tensor rank
with Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami and Swastik Kopparty
- On the power of border of depth-3 arithmetic circuits
This version improves upon the bounds in an earlier version (with a slightly different title)
- Some closure results for polynomial factorization and applications
with Chi-Ning Chou and Noam Solomon
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
with Noga Alon and Ben Lee Volk
Subsumes and improves upon some of the results in an earlier paper with Ben Lee Volk
- A quadratic lower bound for homogeneous algebraic branching programs
- Towards an algebraic natural proofs barrier via polynomial identity testing
with Joshua Grochow, Mike Saks and Shubhangi Saraf
- Finer separations between shallow arithmetic circuits
with Ramprasad Saptharishi
- The Chasm at Depth Four, and Tensor Rank : Old results, new insights
with Suryajith Chillara, Ramprasad Saptharishi and V Vinay
- Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
with Michael A. Forbes and Ramprasad Saptharishi
- Arithmetic circuits with locally low algebraic rank
with Shubhangi Saraf
- An exponential lower bound for homogeneous depth-5 circuits over finite fields
with Ramprasad Saptharishi
- Sums of products of polynomials in few variables : lower bounds and polynomial identity testing
with Shubhangi Saraf
- Efficient indexing of necklaces and irreducible polynomials over finite fields
with Swastik Kopparty and Mike Saks
- On the power of homogeneous depth 4 arithmetic circuits
with Shubhangi Saraf
- Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
with Shubhangi Saraf
- The limits of depth reduction for arithmetic formulas: It's all about the top fan-in
with Shubhangi Saraf
- Lower bounds for depth 4 homogenous circuits with bounded top fanin
with Shubhangi Saraf
- Arithmetic circuit lower bounds via
maximum-rank of partial derivative matrices
with Gaurav Maheshwari and Jayalal Sarma
- Faster parameterized algorithms for deletion to split graphs
with Esha Ghosh, Sudeshna Kolay, Pranabendu Misra, Fahad Panolan, Ashutosh Rai and M.S Ramanujan
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
with Sounaka Mishra, N. Safina Devi and Saket Saurabh