Srikanth Srinivasan

According to our database, Srikanth Srinivasan authored at least 76 papers between 2009 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Commun. ACM, February, 2024

Local Correction of Linear Functions over the Boolean Cube.

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

Electron. Colloquium Comput. Complex., 2024

2023

Schur Polynomials Do Not Have Small Formulas If the Determinant does not.

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

Comput. Complex., June, 2023

Towards Optimal Depth-Reductions for Algebraic Formulas.

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2023

On the Power of Homogeneous Algebraic Formulas.

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2023

The discrepancy of greater-than.

Srikanth Srinivasan, Amir Yehudayoff

CoRR, 2023

Optimal Explicit Small-Depth Formulas for the Coin Problem.

Srikanth Srinivasan, Utkarsh Tripathi

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Low-Degree Testing over Grids.

Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan

Proceedings of the Approximation, 2023

2022

Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

SIGACT News, 2022

On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2022

On the VNP-hardness of Some Monomial Symmetric Polynomials.

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2022

Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes.

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2022

Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication.

Sébastien Tavenas, Nutan Limaye, Srikanth Srinivasan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem.

Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

SIAM J. Comput., 2021

On the Probabilistic Degree of an $n$-variate Boolean Function.

Srikanth Srinivasan, S. Venkitesh

Electron. Colloquium Comput. Complex., 2021

New Non-FPT Lower Bounds for Some Arithmetic Formulas.

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Electron. Colloquium Comput. Complex., 2021

2020

Decoding Variants of Reed-Muller Codes over Finite Grids.

Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

ACM Trans. Comput. Theory, 2020

Local decoding and testing of polynomials over grids.

Mitali Bafna, Srikanth Srinivasan, Madhu Sudan

Random Struct. Algorithms, 2020

A Robust Version of Hegedűs's Lemma, with Applications.

Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2020

2019

Special Issue: CCC 2018: Guest Editor's Foreword.

Srikanth Srinivasan

Theory Comput., 2019

Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications.

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

SIAM J. Comput., 2019

On polynomial approximations to AC.

Prahladh Harsha, Srikanth Srinivasan

Random Struct. Algorithms, 2019

On the Probabilistic Degrees of Symmetric Boolean functions.

Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

Electron. Colloquium Comput. Complex., 2019

Decoding Downset codes over a finite grid.

Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

Electron. Colloquium Comput. Complex., 2019

Strongly Exponential Separation Between Monotone VP and Monotone VNP.

Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2019

Parity helps to compute Majority.

Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2019

More on $AC^0[\oplus]$ and Variants of the Majority Function.

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

Electron. Colloquium Comput. Complex., 2019

Schur Polynomials do not have small formulas if the Determinant doesn't!

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2019

Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees.

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

Comput. Complex., 2019

A fixed-depth size-hierarchy theorem for AC⁰[⊕] via the coin problem.

Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression.

Swastik Kopparty, Srikanth Srinivasan

Theory Comput., 2018

The Coin Problem in Constant Depth: Sample Complexity and Parity gates.

Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh

Electron. Colloquium Comput. Complex., 2018

A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits.

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2018

On the Probabilistic Degree of OR over the Reals.

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2018

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2018

On the hardness of the noncommutative determinant.

Vikraman Arvind, Srikanth Srinivasan

Comput. Complex., 2018

Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds.

Ninad Rajgopal, Rahul Santhanam, Srikanth Srinivasan

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas.

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

SIAM J. Comput., 2017

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes.

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

SIAM J. Comput., 2017

Local decoding and testing of polynomials over grids.

Srikanth Srinivasan, Madhu Sudan

Electron. Colloquium Comput. Complex., 2017

Separation of AC⁰[⊕] Formulas and Circuits.

Benjamin Rossman, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2017

On polynomial approximations over ℤ/2^kℤ.

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2017

On Some Recent Projection Switching Lemmas for Small Depth Circuits.

Srikanth Srinivasan

Bull. EATCS, 2017

On Polynomial Approximations Over Z/2^kZ*.

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Separation of AC^0[oplus] Formulas and Circuits.

Benjamin Rossman, Srikanth Srinivasan

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

On Polynomial Approximations to AC⁰.

Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2016

Robust Multiplication-based Tests for Reed-Muller Codes.

Prahladh Harsha, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2016

An Almost Cubic Lower Bound for ΣΠΣ Circuits Computing a Polynomial in VP.

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2016

Composition limits and separating examples for some boolean function complexity measures.

Justin Gilmer, Michael E. Saks, Srikanth Srinivasan

Comb., 2016

On Polynomial Approximations to AC^0.

Prahladh Harsha, Srikanth Srinivasan

Proceedings of the Approximation, 2016

2015

Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication.

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

SIAM J. Comput., 2015

A tail bound for read-<i>k</i> families of functions.

Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan

Random Struct. Algorithms, 2015

A Compression Algorithm for AC⁰[⊕] circuits using Certifying Polynomials.

Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2015

Lower bounds for non-commutative skew circuits.

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2015

The shifted partial derivative complexity of Elementary Symmetric Polynomials.

Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2015

Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.

Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2015

Derandomized Graph Product Results Using the Low Degree Long Code.

Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

2014

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas.

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Proceedings of the Symposium on Theory of Computing, 2014

2013

On Improved Degree Lower Bounds for Polynomial Approximation.

Srikanth Srinivasan

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

2012

Certifying Polynomials for AC⁰[⊕] circuits, with applications.

Swastik Kopparty, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2012

A Tail Bound for Read-k Families of Functions.

Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2012

Optimal Hitting Sets for Combinatorial Shapes.

Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2012

Certifying polynomials for AC^0(parity) circuits, with applications.

Swastik Kopparty, Srikanth Srinivasan

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

Pseudorandom Generators for Read-Once ACC^0.

Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan

Proceedings of the 27th Conference on Computational Complexity, 2012

Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT.

Paul Beame, Russell Impagliazzo, Srikanth Srinivasan

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

On the Limits of Sparsification.

Rahul Santhanam, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2011

Almost settling the hardness of noncommutative determinant.

Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions.

Andreas Krebs, Nutan Limaye, Srikanth Srinivasan

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 - o(1) Symmetric Gates.

Shachar Lovett, Srikanth Srinivasan

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

New Results on Noncommutative and Commutative Polynomial Identity Testing.

Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

Comput. Complex., 2010

2009

Circuit Lower Bounds, Help Functions, and the Remote Point Problem.

Vikraman Arvind, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2009

The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets.

Vikraman Arvind, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2009

On Lower Bounds for Constant Width Arithmetic Circuits.

Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2009

The Remote Point Problem, Small Bias Space, and Expanding Generator Sets

Vikraman Arvind, Srikanth Srinivasan

CoRR, 2009

Arithmetic Circuits and the Hadamard Product of Polynomials.

Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009