Verified email at gmail.com

Associate Professor, Department of Computer Science

Aarhus University

848

Scholar Citations

18

Scholar h-index

25

Scholar i10-index

- Superpolynomial lower bounds against low-depth algebraic circuits

N Limaye, S Srinivasan, S Tavenas

FOCS 2021 2022 - A# sat algorithm for small constant-depth circuits with PTF gates

S Bajpai, V Krishan, D Kush, N Limaye, S Srinivasan

Algorithmica, 1-31 2022 - On Vanishing Properties of Polynomials on Symmetric Sets of the Boolean Cube, in Positive Characteristic

S Srinivasan, S Venkitesh

arXiv preprint arXiv:2111.05445 2021 - New Non-FPT Lower Bounds for Some Arithmetic Formulas

N Limaye, S Srinivasan, S Tavenas

2021 - On the Probabilistic Degree of OR over the Reals

S Bhandari, P Harsha, T Molli, S Srinivasan

Random Structures & Algorithms 59 (1), 53-67 2021 - On the Probabilistic Degree of an -variate Boolean Function

S Srinivasan, S Venkitesh

arXiv preprint arXiv:2107.03171 2021 - On the probabilistic degrees of symmetric boolean functions

S Srinivasan, U Tripathi, S Venkitesh

SIAM Journal on Discrete Mathematics 35 (3), 2070-2092 2021 - A Fixed-Depth Size-Hierarchy Theorem for via the Coin Problem

N Limaye, K Sreenivasaiah, S Srinivasan, U Tripathi, S Venkitesh

SIAM Journal on Computing 50 (4), 1461-1499 2021 - Decoding Variants of Reed-Muller Codes over Finite Grids

S Srinivasan, U Tripathi, S Venkitesh

ACM Transactions on Computation Theory (TOCT) 12 (4), 1-11 2020 - Local decoding and testing of polynomials over grids

M Bafna, S Srinivasan, M Sudan

Random Structures & Algorithms 57 (3), 658-694 2020 - Strongly exponential separation between monotone VP and monotone VNP

S Srinivasan

ACM Transactions on Computation Theory (TOCT) 12 (4), 1-12 2020 - A robust version of hegedus’s lemma, with applications

S Srinivasan

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing 2020 - More on AC0 [⊕] and Variants of the Majority Function

N Limaye, S Srinivasan, U Tripathi

39th IARCS Annual Conference on Foundations of Software Technology and 2019 - Schur Polynomials do not have small formulas if the Determinant doesn't!

P Chaugule, M Kumar, N Limaye, CK Mohapatra, A She, S Srinivasan

arXiv preprint arXiv:1911.12520 2019 - Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees

G Lagarde, N Limaye, S Srinivasan

computational complexity 28 (3), 471-542 2019 - Decoding Downset codes over a finite grid

S Srinivasan, U Tripathi, S Venkitesh

arXiv preprint arXiv:1908.07215 2019 - Decoding Downset codes over a grid

S Srinivasan, U Tripathi, S Venkitesh

2019 - On polynomial approximations to AC

P Harsha, S Srinivasan

Random Structures & Algorithms 54 (2), 289-303 2019 - More on AC^ 0 [oplus] and Variants of the Majority Function

N Limaye, S Srinivasan, U Tripathi

39th IARCS Annual Conference on Foundations of Software Technology and 2019 - CCC 2018: Guest Editor's Foreword.

S Srinivasan

Theory Comput. 15, 1-3 2019

- Lower bounds for depth-4 formulas computing iterated matrix multiplication

H Fournier, N Limaye, G Malod, S Srinivasan

SIAM Journal on Computing 44 (5), 1173-1201 2015

Citations: 88 - 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

Citations: 80 - New results on noncommutative and commutative polynomial identity testing

V Arvind, P Mukhopadhyay, S Srinivasan

Computational Complexity 19 (4), 521-558 2010

Citations: 47 - 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

Citations: 46 - 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

Citations: 45 - 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

Citations: 38 - Average-case lower bounds and satisfiability algorithms for small threshold circuits

R Chen, R Santhanam, S Srinivasan

arXiv preprint arXiv:1806.06290 2018

Citations: 37 - Composition limits and separating examples for some Boolean function complexity measures

J Gilmer, M Saks, S Srinivasan

Combinatorica 36 (3), 265-311 2016

Citations: 31 - Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

V Guruswami, P Harsha, J Hstad, S Srinivasan, G Varma

SIAM Journal on Computing 46 (1), 132-159 2017

Citations: 28 - Certifying polynomials for AC^ 0 (parity) circuits, with applications

S Kopparty, S Srinivasan

IARCS Annual Conference on Foundations of Software Technology and 2012

Citations: for AC^ 0 (parity) circuits, with applications - Certifying polynomials for AC^ 0 (parity) circuits, with applications

S Kopparty, S Srinivasan

IARCS Annual Conference on Foundations of Software Technology and 2012

Citations: 28 - Arithmetic circuits and the hadamard product of polynomials

V Arvind, PS Joglekar, S Srinivasan

arXiv preprint arXiv:0907.4006 2009

Citations: 28 - On polynomial approximations to AC

P Harsha, S Srinivasan

Random Structures & Algorithms 54 (2), 289-303 2019

Citations: 25 - 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

Citations: 24 - Lower bounds for non-commutative skew circuits

N Limaye, G Malod, S Srinivasan

Theory of Computing 12 (1), 1-38 2016

Citations: 22 - On the limits of sparsification

R Santhanam, S Srinivasan

International Colloquium on Automata, Languages, and Programming, 774-785 2012

Citations: 21 - 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

Citations: 20 - Correlatio n Bou nds for Poly-size $\mbox {\rm AC}^ 0$ Circuits with n1− o (1) Symmetric Gates

S Lovett, S Srinivasan

Approximation, Randomization, and Combinatorial Optimization. Algorithms and 2011

Citations: 20 - 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

Citations: 18 - Streaming algorithms for recognizing nearly well-parenthesized expressions

A Krebs, N Limaye, S Srinivasan

International Symposium on Mathematical Foundations of Computer Science, 412-423 2011

Citations: 17