Srikanth Srinivasan

CoRR, September, 2025

The Algebraic Cost of a Boolean Sum.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Low Degree Local Correction Over the Boolean Cube.

[BibT_eX]

[DOI]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank.

[BibT_eX]

[DOI]

Adarsh Srinivasan

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

New Bounds for the Ideal Proof System in Positive Characteristic.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

A Near-Optimal Polynomial Distance Lemma over Boolean Slices.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2025

2024

On the Power of Homogeneous Algebraic Formulas.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Local Correction of Linear Functions over the Boolean Cube.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

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

[BibT_eX]

[DOI]

Prasad Chaugule

Mrinal Kumar

Chandra Kanta Mohapatra

Adrian She

Comput. Complex., June, 2023

The discrepancy of greater-than.

[BibT_eX]

[DOI]

Amir Yehudayoff

CoRR, 2023

Optimal Explicit Small-Depth Formulas for the Coin Problem.

[BibT_eX]

[DOI]

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

Towards Optimal Depth-Reductions for Algebraic Formulas.

[BibT_eX]

[DOI]

Proceedings of the 38th Computational Complexity Conference, 2023

Low-Degree Testing over Grids.

[BibT_eX]

[DOI]

Prashanth Amireddy

Madhu Sudan

Proceedings of the Approximation, 2023

2022

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

[BibT_eX]

[DOI]

SIGACT News, 2022

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

[BibT_eX]

[DOI]

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

On the VNP-Hardness of Some Monomial Symmetric Polynomials.

[BibT_eX]

[DOI]

Radu Curticapean

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

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

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

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

[BibT_eX]

[DOI]

Siddharth Bhandari

Ramprasad Saptharishi

Proceedings of the 37th Computational Complexity Conference, 2022

2021

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

[BibT_eX]

[DOI]

Karteek Sreenivasaiah

SIAM J. Comput., 2021

New Non-FPT Lower Bounds for Some Arithmetic Formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

On the Probabilistic Degree of an n-Variate Boolean Function.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Decoding Variants of Reed-Muller Codes over Finite Grids.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2020

Local decoding and testing of polynomials over grids.

[BibT_eX]

[DOI]

Mitali Bafna

Madhu Sudan

Random Struct. Algorithms, 2020

A robust version of Hegedus's lemma, with applications.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't.

[BibT_eX]

[DOI]

Prasad Chaugule

Mrinal Kumar

Chandra Kanta Mohapatra

Adrian She

Proceedings of the 35th Computational Complexity Conference, 2020

2019

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

[BibT_eX]

[DOI]

Theory Comput., 2019

On polynomial approximations to AC.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2019

Decoding Downset codes over a finite grid.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Strongly Exponential Separation Between Monotone VP and Monotone VNP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

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

[BibT_eX]

[DOI]

Karteek Sreenivasaiah

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

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

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

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

[BibT_eX]

[DOI]

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

On the Probabilistic Degrees of Symmetric Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Parity Helps to Compute Majority.

[BibT_eX]

[DOI]

Igor Carboni Oliveira

Proceedings of the 34th Computational Complexity Conference, 2019

2018

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

[BibT_eX]

[DOI]

Swastik Kopparty

Theory Comput., 2018

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

[BibT_eX]

[DOI]

Karteek Sreenivasaiah

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Suryajith Chillara

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

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

[BibT_eX]

[DOI]

Ninad Rajgopal

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

Local Decoding and Testing of Polynomials over Grids.

[BibT_eX]

[DOI]

Madhu Sudan

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

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

[BibT_eX]

[DOI]

Suryajith Chillara

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

On the Probabilistic Degree of OR over the Reals.

[BibT_eX]

[DOI]

Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

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

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Separation of AC0[⊕] Formulas and Circuits.

[BibT_eX]

[DOI]

Benjamin Rossman

Electron. Colloquium Comput. Complex., 2017

On polynomial approximations over ℤ/2kℤ.

[BibT_eX]

[DOI]

Abhishek Bhrushundi

Electron. Colloquium Comput. Complex., 2017

On Some Recent Projection Switching Lemmas for Small Depth Circuits.

[BibT_eX]

[DOI]

Bull. EATCS, 2017

On Polynomial Approximations Over Z/2^kZ*.

[BibT_eX]

[DOI]

Abhishek Bhrushundi

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

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

[BibT_eX]

[DOI]

Guillaume Lagarde

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

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

[BibT_eX]

[DOI]

Benjamin Rossman

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

2016

On Polynomial Approximations to AC0.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

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

[BibT_eX]

[DOI]

Nikhil Balaji

Electron. Colloquium Comput. Complex., 2016

Robust Multiplication-Based Tests for Reed-Muller Codes.

[BibT_eX]

[DOI]

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

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

[BibT_eX]

[DOI]

Ruiwen Chen

Proceedings of the 31st Conference on Computational Complexity, 2016

On Polynomial Approximations to AC^0.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

A tail bound for read-k families of functions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2015

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Lower bounds for non-commutative skew circuits.

[BibT_eX]

[DOI]

Guillaume Malod

Electron. Colloquium Comput. Complex., 2015

Derandomized Graph Product Results Using the Low Degree Long Code.

[BibT_eX]

[DOI]

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

The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014

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

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Lower bounds for depth 4 formulas computing iterated matrix multiplication.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

On Improved Degree Lower Bounds for Polynomial Approximation.

[BibT_eX]

[DOI]

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

Composition Limits and Separating Examples for Some Boolean Function Complexity Measures.

[BibT_eX]

[DOI]

Justin Gilmer

Michael E. Saks

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Certifying Polynomials for AC0[⊕] circuits, with applications.

[BibT_eX]

[DOI]

Swastik Kopparty

Electron. Colloquium Comput. Complex., 2012

A Tail Bound for Read-k Families of Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

On the Limits of Sparsification.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

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

[BibT_eX]

[DOI]

Swastik Kopparty

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

Pseudorandom Generators for Read-Once ACC^0.

[BibT_eX]

[DOI]

Dmitry Gavinsky

Shachar Lovett

Proceedings of the 27th Conference on Computational Complexity, 2012

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

[BibT_eX]

[DOI]

Paul Beame

Russell Impagliazzo

Proceedings of the 27th Conference on Computational Complexity, 2012

Optimal Hitting Sets for Combinatorial Shapes.

[BibT_eX]

[DOI]

Aditya Bhaskara

Devendra Desai

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

2011

Almost settling the hardness of noncommutative determinant.

[BibT_eX]

[DOI]

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

Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions.

[BibT_eX]

[DOI]

Andreas Krebs

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.

[BibT_eX]

[DOI]

Shachar Lovett

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

2010

On the hardness of the noncommutative determinant.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

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

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

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

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2010

2009

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

[BibT_eX]

[DOI]

CoRR, 2009

On Lower Bounds for Constant Width Arithmetic Circuits.

[BibT_eX]

[DOI]

Pushkar S. Joglekar

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Arithmetic Circuits and the Hadamard Product of Polynomials.

[BibT_eX]

[DOI]

Pushkar S. Joglekar

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

2008

New Results on Noncommutative and Commutative Polynomial Identity Testing.

[BibT_eX]

[DOI]

Partha Mukhopadhyay