Srikanth Srinivasan

Verified email at gmail.com

Associate Professor, Department of Computer Science
Aarhus University



                       

https://researchid.co/srikanthsrinivasan
848

Scholar Citations

18

Scholar h-index

25

Scholar i10-index

RECENT SCHOLAR PUBLICATIONS

  • 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

MOST CITED SCHOLAR PUBLICATIONS

  • 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