Srikanth Srinivasan

@cs.au.dk

Associate Professor, Department of Computer Science
Aarhus University



           

https://researchid.co/srikanthsrinivasan
1132

Scholar Citations

20

Scholar h-index

29

Scholar i10-index

RECENT SCHOLAR PUBLICATIONS

  • Low Degree Local Correction Over the Boolean Cube
    P Amireddy, AR Behera, M Paraashar, S Srinivasan, M Sudan
    arXiv preprint arXiv:2411.07374 2024

  • 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

  • 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

  • Superpolynomial lower bounds against low-depth algebraic circuits
    N Limaye, S Srinivasan, S Tavenas
    Communications of the ACM 67 (2), 101-108 2024

  • 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
    P Bouyer, S Srinivasan
     2023

  • The discrepancy of greater-than
    S Srinivasan, A Yehudayoff
    arXiv preprint arXiv:2309.08703 2023

  • Optimal Explicit Small-Depth Formulas for the Coin Problem
    S Srinivasan, U Tripathi
    Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 881-894 2023

  • Schur Polynomials Do Not Have Small Formulas If the Determinant does not
    P Chaugule, M Kumar, N Limaye, CK Mohapatra, A She, S Srinivasan
    computational complexity 32 (1), 3 2023

  • Low-degree testing over grids
    P Amireddy, S Srinivasan, M Sudan
    arXiv preprint arXiv:2305.04983 2023

  • Towards Optimal Depth-Reductions for Algebraic Formulas
    H Fournier, N Limaye, G Malod, S Srinivasan, S Tavenas
    arXiv preprint arXiv:2302.06984 2023

  • 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2023, December 18-20, 2023, IIIT Hyderabad, Telangana, India
    P Bouyer, S Srinivasan
    Schloss Dagstuhl-Leibniz-Zentrum fr Informatik GmbH 2023

  • LIPIcs, Volume 284, FSTTCS 2023, Complete Volume
    P Bouyer, S Srinivasan
    43rd IARCS Annual Conference on Foundations of Software Technology and 2023

  • On the partial derivative method applied to lopsided set-multilinear polynomials
    N Limaye, S Srinivasan, S Tavenas
    37th Computational Complexity Conference (CCC 2022) 2022

  • Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits
    N Limaye, S Srinivasan, S Tavenas
    ACM SIGACT News 53 (2), 40-62 2022

  • 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

  • Vanishing spaces of random sets and applications to Reed-Muller codes
    S Bhandari, P Harsha, R Saptharishi, S Srinivasan
    arXiv preprint arXiv:2205.10749 2022

  • Lower bounds Against Constant-Depth Algebraic Circuits
    N Limaye, S Srinivasan, S Tavenas
     2022

  • A# sat algorithm for small constant-depth circuits with PTF gates
    S Bajpai, V Krishan, D Kush, N Limaye, S Srinivasan
    Algorithmica 84 (4), 1132-1162 2022

  • 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
    A Gupta, R Santhanam, P Bouyer, M Randour, P Vandenhove, I Dinur, ...
    Schloss Dagstuhl-Leibniz-Zentrum fr Informatik GmbH 2022

  • On the VNP-Hardness of Some Monomial Symmetric Polynomials
    R Curticapean, N Limaye, S Srinivasan
    42nd IARCS Annual Conference on Foundations of Software Technology and 2022

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

  • 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: 91

  • Superpolynomial lower bounds against low-depth algebraic circuits
    N Limaye, S Srinivasan, S Tavenas
    Communications of the ACM 67 (2), 101-108 2024
    Citations: 63

  • New results on noncommutative and commutative polynomial identity testing
    V Arvind, P Mukhopadhyay, S Srinivasan
    Computational Complexity 19 (4), 521-558 2010
    Citations: 56

  • 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: 54

  • 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: 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
    Citations: 49

  • Average-case lower bounds and satisfiability algorithms for small threshold circuits
    R Chen, R Santhanam, S Srinivasan
    arXiv preprint arXiv:1806.06290 2018
    Citations: 48

  • Composition limits and separating examples for some Boolean function complexity measures
    J Gilmer, M Saks, S Srinivasan
    Combinatorica 36 (3), 265-311 2016
    Citations: 47

  • On polynomial approximations to AC
    P Harsha, S Srinivasan
    Random Structures & Algorithms 54 (2), 289-303 2019
    Citations: 34

  • Arithmetic circuits and the hadamard product of polynomials
    V Arvind, PS Joglekar, S Srinivasan
    arXiv preprint arXiv:0907.4006 2009
    Citations: 32

  • 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: 29

  • Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
    V Guruswami, P Harsha, J Hstad, S Srinivasan, G Varma
    Proceedings of the forty-sixth annual ACM symposium on Theory of computing 2014
    Citations: 29

  • Certifying polynomials for AC^ 0 (parity) circuits, with applications
    S Kopparty, S Srinivasan
    IARCS Annual Conference on Foundations of Software Technology and 2012
    Citations: 29

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

  • On the limits of sparsification
    R Santhanam, S Srinivasan
    Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012
    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: 23

  • 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
    Citations: 23

  • 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: 22