Towards optimal depth-reductions for algebraic formulas H Fournier, N Limaye, G Malod, S Srinivasan, S Tavenas computational complexity 35 (1), 3 , 2026 2026 Citations: 3
Separation Results for Constant-Depth and Multilinear Ideal Proof Systems AR Behera, MRD Hansen, N Limaye, S Srinivasan arXiv preprint arXiv:2601.06299 , 2026 2026 Citations: 1
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs R Andrews, J Armand, P Dwivedi, MRD Hansen, N Limaye, S Srinivasan, ... 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), 9 … , 2026 2026
Negations are powerful even in small depth B Cavalar, TB Fabris, P Mukhopadhyay, S Srinivasan, A Yehudayoff arXiv preprint arXiv:2512.19515 , 2025 2025
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs J Armand, P Dwivedi, MRD Hansen, N Limaye, S Srinivasan, S Tavenas arXiv preprint arXiv:2509.10725 , 2025 2025
40th Computational Complexity Conference S Srinivasan 2025
Superpolynomial lower bounds against low-depth algebraic circuits N Limaye, S Srinivasan, S Tavenas Journal of the ACM 72 (4), 1-35 , 2025 2025 Citations: 93
Eigenvalue bounds for symmetric markov chains on multislices with applications P Amireddy, AR Behera, S Srinivasan, M Sudan arXiv preprint arXiv:2507.10731 , 2025 2025
A Near-Optimal Polynomial Distance Lemma over Boolean Slices P Amireddy, AR Behera, S Srinivasan, M Sudan arXiv preprint arXiv:2507.03193 , 2025 2025 Citations: 2
New bounds for the ideal proof system in positive characteristic AR Behera, N Limaye, V Ramanathan, S Srinivasan arXiv preprint arXiv:2506.16397 , 2025 2025 Citations: 6
The Algebraic Cost of a Boolean Sum I Orzel, S Srinivasan, S Tavenas, A Yehudayoff arXiv preprint arXiv:2502.02442 , 2025 2025
# SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank N Limaye, A Srinivasan, S Srinivasan 50th International Symposium on Mathematical Foundations of Computer Science … , 2025 2025
Low Degree Local Correction Over the Boolean Cube P Amireddy, AR Behera, M Paraashar, S Srinivasan, M Sudan Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms … , 2025 2025 Citations: 2
On the power of homogeneous algebraic formulas H Fournier, N Limaye, S Srinivasan, S Tavenas Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 141-151 , 2024 2024 Citations: 7
Local correction of linear functions over the boolean cube P Amireddy, AR Behera, M Paraashar, S Srinivasan, M Sudan Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 764-775 , 2024 2024 Citations: 4
Superpolynomial lower bounds against low-depth algebraic circuits N Limaye, S Srinivasan, S Tavenas Communications of the ACM 67 (2), 101-108 , 2024 2024 Citations: 10
Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) P Bouyer, S Srinivasan Schloss Dagstuhl–Leibniz-Zentrum für Informatik , 2023 2023
43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science P Bouyer, S Srinivasan 2023
MOST CITED SCHOLAR PUBLICATIONS
Lower bounds for depth 4 formulas computing iterated matrix multiplication H Fournier, N Limaye, G Malod, S Srinivasan Proceedings of the forty-sixth annual ACM symposium on Theory of computing … , 2014 2014 Citations: 98
Superpolynomial lower bounds against low-depth algebraic circuits N Limaye, S Srinivasan, S Tavenas Journal of the ACM 72 (4), 1-35 , 2025 2025 Citations: 93
An exponential lower bound for homogeneous depth four arithmetic formulas N Kayal, N Limaye, C Saha, S Srinivasan SIAM Journal on Computing 46 (1), 307-335 , 2017 2017 Citations: 87
A tail bound for read‐ k families of functions D Gavinsky, S Lovett, M Saks, S Srinivasan Random Structures & Algorithms 47 (1), 99-108 , 2015 2015 Citations: 66
New results on noncommutative and commutative polynomial identity testing V Arvind, P Mukhopadhyay, S Srinivasan Computational Complexity 19 (4), 521-558 , 2010 2010 Citations: 57
Composition limits and separating examples for some Boolean function complexity measures J Gilmer, M Saks, S Srinivasan Combinatorica 36 (3), 265-311 , 2016 2016 Citations: 53
Approximating ac^ 0 by small height decision trees and a deterministic algorithm for# ac^ 0sat P Beame, R Impagliazzo, S Srinivasan 2012 IEEE 27th Conference on Computational Complexity, 117-125 , 2012 2012 Citations: 52
Average-case lower bounds and satisfiability algorithms for small threshold circuits R Chen, R Santhanam, S Srinivasan arXiv preprint arXiv:1806.06290 , 2018 2018 Citations: 50
On the hardness of the noncommutative determinant V Arvind, S Srinivasan Proceedings of the forty-second ACM symposium on Theory of computing, 677-686 , 2010 2010 Citations: 50
On polynomial approximations to AC P Harsha, S Srinivasan Random Structures & Algorithms 54 (2), 289-303 , 2019 2019 Citations: 38
Arithmetic circuits and the hadamard product of polynomials V Arvind, PS Joglekar, S Srinivasan arXiv preprint arXiv:0907.4006 , 2009 2009 Citations: 33
Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications S Chillara, N Limaye, S Srinivasan SIAM Journal on Computing 48 (1), 70-92 , 2019 2019 Citations: 30
Certifying polynomials for AC^ 0 (parity) circuits, with applications S Kopparty, S Srinivasan IARCS Annual Conference on Foundations of Software Technology and … , 2012 2012 Citations: 30
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes V Guruswami, P Harsha, J Håstad, S Srinivasan, G Varma Proceedings of the forty-sixth annual ACM symposium on Theory of computing … , 2014 2014 Citations: 28
On the limits of sparsification R Santhanam, S Srinivasan International Colloquium on Automata, Languages, and Programming, 774-785 , 2012 2012 Citations: 28
A near-optimal depth-hierarchy theorem for small-depth multilinear circuits S Chillara, C Engels, N Limaye, S Srinivasan 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS … , 2018 2018 Citations: 27
Correlation Bounds for Poly-size Circuits with n 1− o (1) Symmetric Gates S Lovett, S Srinivasan International Workshop on Approximation Algorithms for Combinatorial … , 2011 2011 Citations: 26
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication S Tavenas, N Limaye, S Srinivasan Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing … , 2022 2022 Citations: 25
Lower bounds for non-commutative skew circuits N Limaye, G Malod, S Srinivasan Theory of Computing 12 (1), 1-38 , 2016 2016 Citations: 24
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas N Kayal, N Limaye, C Saha, S Srinivasan Proceedings of the forty-sixth annual ACM symposium on Theory of computing … , 2014 2014 Citations: 22
