Research outputs

Filter research outputs

What type of research output do you want to show?

All

Chapter

Conference Paper

Journal

Preprint

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 Leibniz International Proceedings in Informatics Lipics Vol. 345. doi:10.4230/LIPIcs.MFCS.2025.17

DOI: 10.4230/LIPIcs.MFCS.2025.17
: Conference Paper

Sensitivity and Query Complexity under Uncertainty

DOI: 10.48550/arxiv.2507.00148
: Preprint

2024

Query Complexity with Unknowns

DOI: 10.48550/arxiv.2412.06395
: Preprint

Depth-3 Circuit Lower Bounds for k-OV

Choudhury, T., & Sreenivasaiah, K. (2024). Depth-3 Circuit Lower Bounds for k-OV. In 41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024 Vol. 289. doi:10.4230/LIPIcs.STACS.2024.25

DOI: 10.4230/LIPIcs.STACS.2024.25
: Conference Paper

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. doi:10.1016/j.ipl.2023.106418

DOI: 10.1016/j.ipl.2023.106418
: Journal article

2021

A FIXED-DEPTH SIZE-HIERARCHY THEOREM FOR AC0[⊕] VIA THE COIN PROBLEM

Limaye, N., Sreenivasaiah, K., Srinivasan, S., Tripathi, U., & Venkitesh, S. (2021). A FIXED-DEPTH SIZE-HIERARCHY THEOREM FOR AC0[⊕] VIA THE COIN PROBLEM. SIAM JOURNAL ON COMPUTING, 50(4), 1461-1499. doi:10.1137/19M1276467

DOI: 10.1137/19M1276467
: Journal article

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

DOI: 10.1016/j.jcss.2016.11.011
: Journal article

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

DOI: 10.1145/3320123
: Journal article

A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] via the Coin Problem

Limaye, N., Sreenivasaiah, K., Srinivasan, S., Tripathi, U., & Venkitesh, S. (2019). A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] 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

DOI: 10.1145/3313276.3316339
: Conference Paper

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

DOI: 10.4230/LIPIcs.FSTTCS.2018.18
: Conference Paper

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

DOI: 10.1145/3188745.3188912
: Journal article

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

DOI: 10.1007/978-3-662-55751-8_19
: Chapter

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

DOI: 10.1007/978-3-662-55751-8_19
: Conference Paper

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

DOI: 10.1007/s00453-015-0101-z
: Journal article

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

DOI: 10.1145/2956229
: Journal article

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

DOI: 10.1145/2894843
: Journal article

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

DOI: 10.1007/978-3-319-15579-1_38
: Conference Paper

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

DOI: 10.1016/j.tcs.2014.01.005
: Journal article

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/

: Conference Paper

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/

: Chapter

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

DOI: 10.1145/2462896.2462898
: Journal article

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

DOI: 10.1007/978-3-642-32241-9_39
: Chapter

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/

: Chapter

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).

: Conference Paper

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/

: Chapter

Dr Karteek Sreenivasaiah