Ramprasad Saptharishi
Title
Cited by
Cited by
Year
Approaching the chasm at depth four
A Gupta, P Kamath, N Kayal, R Saptharishi
Journal of the ACM (JACM) 61 (6), 1-16, 2014
1132014
Arithmetic circuits: A chasm at depth three
A Gupta, P Kamath, N Kayal, R Saptharishi
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 578-587, 2013
1092013
A super-polynomial lower bound for regular arithmetic formulas
N Kayal, C Saha, R Saptharishi
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
762014
Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth- Occur- Formulas and Depth-3 Transcendence Degree- Circuits
M Agrawal, C Saha, R Saptharishi, N Saxena
SIAM Journal on Computing 45 (4), 1533-1562, 2016
652016
A survey of lower bounds in arithmetic circuit complexity
R Saptharishi
Github survey, 2015
552015
Fast integer multiplication using modular arithmetic
A De, PP Kurur, C Saha, R Saptharishi
Proceedings of the fortieth annual ACM symposium on Theory of computing, 499-506, 2008
552008
Fast integer multiplication using modular arithmetic
A De, PP Kurur, C Saha, R Saptharishi
SIAM Journal on Computing 42 (2), 685-699, 2013
472013
Hitting sets for multilinear read-once algebraic branching programs, in any order
MA Forbes, R Saptharishi, A Shpilka
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
462014
Arithmetic circuits: A chasm at depth 3
A Gupta, P Kamath, N Kayal, R Saptharishi
SIAM Journal on Computing 45 (3), 1064-1079, 2016
302016
A case of depth-3 identity testing, sparse factorization and duality
C Saha, R Saptharishi, N Saxena
Computational Complexity 22 (1), 39-69, 2013
282013
Classifying polynomials and identity testing
M Agrawal, R SaptharishiI
Indian Academy of Sciences, 2009
232009
Efficiently decoding Reed-Muller codes from random errors
R Saptharishi, A Shpilka, BL Volk
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
202016
An exponential lower bound for homogeneous depth-5 circuits over finite fields
M Kumar, R Saptharishi
arXiv preprint arXiv:1507.00177, 2015
202015
The power of depth 2 circuits over algebras
C Saha, R Saptharishi, N Saxena
arXiv preprint arXiv:0904.2058, 2009
202009
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs
M Anderson, MA Forbes, R Saptharishi, A Shpilka, BL Volk
ACM Transactions on Computation Theory (TOCT) 10 (1), 1-30, 2018
192018
A selection of lower bounds for arithmetic circuits
N Kayal, R Saptharishi
Perspectives in computational complexity, 77-115, 2014
152014
Near-optimal bootstrapping of hitting sets for algebraic circuits
M Kumar, R Saptharishi, A Tengse
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019
122019
The chasm at depth four, and tensor rank: Old results, new insights
S Chillara, M Kumar, R Saptharishi, V Vinay
arXiv preprint arXiv:1606.04200, 2016
122016
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
MA Forbes, M Kumar, R Saptharishi
arXiv preprint arXiv:1605.04207, 2016
102016
A survey of lower bounds in arithmetic circuit complexity, 2016
R Saptharishi
Available at author’s GitHub 3, 14, 2016
92016
The system can't perform the operation now. Try again later.
Articles 1–20