Publications
2024
Depth-3 Circuit Lower Bounds for k-OV
Choudhury, T., & Sreenivasaiah, K. (2024). Depth-3 Circuit Lower Bounds for k-OV. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 289. doi:10.4230/LIPIcs.STACS.2024.25
Linear threshold functions in decision lists, decision trees, and depth-2 circuits
Dahiya, Y., K., V., Mahajan, M., & Sreenivasaiah, K. (2024). Linear threshold functions in decision lists, decision trees, and depth-2 circuits. Information Processing Letters, 183, 106418. doi:10.1016/j.ipl.2023.106418
2021
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
Limaye, N., Sreenivasaiah, K., Srinivasan, S., Tripathi, U., & Venkitesh, S. (2021). A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ 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 (pp. 442-453). ACM. 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
2017
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
Small Depth Proof Systems
Krebs, A., Limaye, N., Mahajan, M., & Sreenivasaiah, K. (2017). Small Depth Proof Systems. ACM Transactions on Computation Theory, 9(1), 1-26. doi:10.1145/2956229
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 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 10472 LNCS (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
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), 1-28. 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 Unknown Conference (pp. 486-498). Springer International Publishing. 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 Unknown Conference (pp. 1-12). Springer International Publishing. doi:10.1007/978-3-319-08783-2_1
2013
Small Depth Proof Systems
Krebs, A., Limaye, N., Mahajan, M., & Sreenivasaiah, K. (2013). Small Depth Proof Systems. In Lecture Notes in Computer Science (pp. 583-594). Springer Berlin Heidelberg. doi:10.1007/978-3-642-40313-2_52
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), 1-23. 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 Lecture Notes in Computer Science (pp. 458-469). Springer Berlin Heidelberg. 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 Lecture Notes in Computer Science (pp. 655-667). Springer Berlin Heidelberg. doi:10.1007/978-3-642-32589-2_57
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 Lecture Notes in Computer Science (pp. 84-95). Springer Berlin Heidelberg. doi:10.1007/978-3-642-22993-0_11