Research outputs
2026
Depth-3 Circuit Lower Bounds for k-OV
Choudhury, T., & Sreenivasaiah, K. (2026). Depth-3 Circuit Lower Bounds for k-OV. ACM Transactions on Computation Theory. doi:10.1145/3812802
2025
Sensitivity and Query Complexity Under Uncertainty
Benson, D., Komarath, B., Mande, N., Nalli, S. S., Sarma, J., & Sreenivasaiah, K. (2025). Sensitivity and Query Complexity Under Uncertainty. In 50TH INTERNATIONAL SYMPOSIUM ON MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE, MFCS 2025 Vol. 345 (pp. 17 pages). doi:10.4230/LIPIcs.MFCS.2025.17
2024
Depth-3 Circuit Lower Bounds for <i>k</i>-OV
Choudhury, T., & Sreenivasaiah, K. (2024). Depth-3 Circuit Lower Bounds for <i>k</i>-OV. In 41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024 Vol. 289 (pp. 17 pages). doi:10.4230/LIPIcs.STACS.2024.25
Linear threshold functions in decision lists, decision trees, and depth-2 circuits
Dahiya, Y., Vignesh, K., Mahajan, M., & Sreenivasaiah, K. (2024). Linear threshold functions in decision lists, decision trees, and depth-2 circuits. INFORMATION PROCESSING LETTERS, 183, 4 pages. doi:10.1016/j.ipl.2023.106418
2021
A FIXED-DEPTH SIZE-HIERARCHY THEOREM FOR AC<SUP>0</SUP>[⊕] VIA THE COIN PROBLEM
Limaye, N., Sreenivasaiah, K., Srinivasan, S., Tripathi, U., & Venkitesh, S. (2021). A FIXED-DEPTH SIZE-HIERARCHY THEOREM FOR AC<SUP>0</SUP>[⊕] VIA THE COIN PROBLEM. SIAM JOURNAL ON COMPUTING, 50(4), 1461-1499. doi:10.1137/19M1276467
2019
A game characterisation of tree-like Q-Resolution size
Beyersdorff, O., Chew, L., & Sreenivasaiah, K. (2019). A game characterisation of tree-like Q-Resolution size. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 104, 82-101. doi:10.1016/j.jcss.2016.11.011
On the Complexity of Hazard-free Circuits
Ikenmeyer, C., Komarath, B., Lenzen, C., Lysikov, V., Mokhov, A., & Sreenivasaiah, K. (2019). On the Complexity of Hazard-free Circuits. JOURNAL OF THE ACM, 66(4). doi:10.1145/3320123
A Fixed-Depth Size-Hierarchy Theorem for AC<SUP>0</SUP>[⊕] via the Coin Problem
Limaye, N., Sreenivasaiah, K., Srinivasan, S., Tripathi, U., & Venkitesh, S. (2019). A Fixed-Depth Size-Hierarchy Theorem for AC<SUP>0</SUP>[⊕] via the Coin Problem. In PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19) (pp. 442-453). doi:10.1145/3313276.3316339
2018
Graph pattern polynomials
Bläser, M., Komarath, B., & Sreenivasaiah, K. (2018). Graph pattern polynomials. In Leibniz International Proceedings in Informatics Lipics Vol. 122. doi:10.4230/LIPIcs.FSTTCS.2018.18
On the Complexity of Hazard-Free Circuits
Ikenmeyer, C., Komarath, B., Lenzen, C., Lysikov, V., Mokhov, A., & Sreenivasaiah, K. (2018). On the Complexity of Hazard-Free Circuits. STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 878-889. doi:10.1145/3188745.3188912
2017
On $$\varSigma \wedge \varSigma \wedge \varSigma $$ Circuits: The Role of Middle $$\varSigma $$ Fan-In, Homogeneity and Bottom Degree
Engels, C., Rao, B. V. R., & Sreenivasaiah, K. (2017). On $$\varSigma \wedge \varSigma \wedge \varSigma $$ Circuits: The Role of Middle $$\varSigma $$ Fan-In, Homogeneity and Bottom Degree. In Lecture Notes in Computer Science (pp. 230-242). Springer Berlin Heidelberg. doi:10.1007/978-3-662-55751-8_19
On Σ ∧ Σ ∧ Σ Circuits: The Role of Middle Σ Fan-In, Homogeneity and Bottom Degree
Engels, C., Rao, B. V. R., & Sreenivasaiah, K. (2017). On Σ ∧ Σ ∧ Σ Circuits: The Role of Middle Σ Fan-In, Homogeneity and Bottom Degree. In FUNDAMENTALS OF COMPUTATION THEORY, FCT 2017 Vol. 10472 (pp. 230-242). doi:10.1007/978-3-662-55751-8_19
2016
Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation
Mahajan, M., Rao, B. V. R., & Sreenivasaiah, K. (2016). Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation. ALGORITHMICA, 76(4), 890-909. doi:10.1007/s00453-015-0101-z
Small depth proof systems
Krebs, A., Limaye, N., Mahajan, M., & Sreenivasaiah, K. (2016). Small depth proof systems. ACM Transactions on Computation Theory, 9(1). doi:10.1145/2956229
Space-efficient approximations for subset sum
Gál, A., Jang, J. T., Limaye, N., Mahajan, M., & Sreenivasaiah, K. (2016). Space-efficient approximations for subset sum. ACM Transactions on Computation Theory, 8(4). doi:10.1145/2894843
2015
A game characterisation of tree-like q-resolution size
Beyersdorff, O., Chew, L., & Sreenivasaiah, K. (2015). A game characterisation of tree-like q-resolution size. In Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics Vol. 8977 (pp. 486-498). doi:10.1007/978-3-319-15579-1_38
2014
Monomials, multilinearity and identity testing in simple read-restricted circuits
Mahajan, M., Rao, B. V. R., & Sreenivasaiah, K. (2014). Monomials, multilinearity and identity testing in simple read-restricted circuits. THEORETICAL COMPUTER SCIENCE, 524, 90-102. doi:10.1016/j.tcs.2014.01.005
Building above Read-once Polynomials: Identity Testing and Hardness of Representation
Mahajan, M., Rao, B. V. R., & Sreenivasaiah, K. (2014). Building above Read-once Polynomials: Identity Testing and Hardness of Representation. In COMPUTING AND COMBINATORICS, COCOON 2014 Vol. 8591 (pp. 1-12). Retrieved from https://www.webofscience.com/
2013
Small Depth Proof Systems
Krebs, A., Limaye, N., Mahajan, M., & Sreenivasaiah, K. (2013). Small Depth Proof Systems. In Unknown Book (Vol. 8087, pp. 583-594). Retrieved from https://www.webofscience.com/
Verifying proofs in constant depth
Beyersdorff, O., Datta, S., Krebs, A., Mahajan, M., Scharfenberger-Fabian, G., Sreenivasaiah, K., . . . Vollmer, H. (2013). Verifying proofs in constant depth. ACM Transactions on Computation Theory, 5(1). doi:10.1145/2462896.2462898
2012
The complexity of unary subset sum
Limaye, N., Mahajan, M., & Sreenivasaiah, K. (2012). The complexity of unary subset sum. In Unknown Book (Vol. 7434 LNCS, pp. 458-469). doi:10.1007/978-3-642-32241-9_39
Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs
Mahajan, M., Rao, B. V. R., & Sreenivasaiah, K. (2012). Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs. In Unknown Book (Vol. 7464, pp. 655-667). Retrieved from https://www.webofscience.com/
Counting paths in planar width 2 branching programs
Mahajan, M., Saurabh, N., & Sreenivasaiah, K. (2012). Counting paths in planar width 2 branching programs. In Conferences in Research and Practice in Information Technology Series Vol. 128 (pp. 59-68).
2011
Verifying Proofs in Constant Depth
Beyersdorff, O., Datta, S., Mahajan, M., Scharfenberger-Fabian, G., Sreenivasaiah, K., Thomas, M., & Vollmer, H. (2011). Verifying Proofs in Constant Depth. In Unknown Book (Vol. 6907, pp. 84-95). Retrieved from https://www.webofscience.com/