publications

Please see my DBLP for a full list

2024

  1. Linear threshold functions in decision lists, decision trees, and depth-2 circuits
    Dahiya, Yogesh, K, Vignesh, Mahajan, Meena, and Sreenivasaiah, Karteek
    IPL 2024
    DOI pdf

2021

  1. A Fixed-Depth Size-Hierarchy Theorem for AC\(^0\)[\(⊕\)] via the Coin Problem
    Limaye, Nutan,  Sreenivasaiah, Karteek, Srinivasan, Srikanth, Tripathi, Utkarsh, and Venkitesh, S.
    SIAM J. Comput. 2021
    DOI pdf

2019

  1. On the Complexity of Hazard-free Circuits
    Ikenmeyer, Christian, Komarath, Balagopal, Lenzen, Christoph, Lysikov, Vladimir, Mokhov, Andrey, and Sreenivasaiah, Karteek
    J. ACM 2019
    DOI pdf
  2. A game characterisation of tree-like Q-Resolution size
    Beyersdorff, Olaf, Chew, Leroy, and Sreenivasaiah, Karteek
    J. Comput. Syst. Sci. 2019
    DOI pdf
  3. A fixed-depth size-hierarchy theorem for AC\(^0\)[\(⊕\)] via the coin problem
    Limaye, Nutan,  Sreenivasaiah, Karteek, Srinivasan, Srikanth, Tripathi, Utkarsh, and Venkitesh, S.
    In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 2019
    DOI pdf

2018

  1. Graph Pattern Polynomials
    Bläser, Markus, Komarath, Balagopal, and Sreenivasaiah, Karteek
    In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India 2018
    DOI pdf
  2. On the complexity of hazard-free circuits
    Ikenmeyer, Christian, Komarath, Balagopal, Lenzen, Christoph, Lysikov, Vladimir, Mokhov, Andrey, and Sreenivasaiah, Karteek
    In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 2018
    DOI pdf

2017

  1. On ∑ ⋀ ∑ ⋀ ∑Circuits: The Role of Middle ∑  Fan-In, Homogeneity and Bottom Degree
    Engels, Christian, Rao, B. V. Raghavendra, and Sreenivasaiah, Karteek
    In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings 2017
    DOI pdf

2016

  1. Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation
    Mahajan, Meena, Rao, B. V. Raghavendra, and Sreenivasaiah, Karteek
    Algorithmica 2016
    DOI pdf
  2. Space-Efficient Approximations for Subset Sum
    Gál, Anna, Jang, Jing-Tang, Limaye, Nutan, Mahajan, Meena, and Sreenivasaiah, Karteek
    ACM Trans. Comput. Theory 2016
    DOI pdf
  3. Small Depth Proof Systems
    Krebs, Andreas, Limaye, Nutan, Mahajan, Meena, and Sreenivasaiah, Karteek
    ACM Trans. Comput. Theory 2016
    DOI pdf

2015

  1. A Game Characterisation of Tree-like Q-resolution Size
    Beyersdorff, Olaf, Chew, Leroy, and Sreenivasaiah, Karteek
    In Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings 2015
    DOI pdf

2014

  1. Monomials, multilinearity and identity testing in simple read-restricted circuits
    Mahajan, Meena, Rao, B. V. Raghavendra, and Sreenivasaiah, Karteek
    Theor. Comput. Sci. 2014
    DOI pdf
  2. Building above Read-once Polynomials: Identity Testing and Hardness of Representation
    Mahajan, Meena, Rao, B. V. Raghavendra, and Sreenivasaiah, Karteek
    In Computing and Combinatorics - 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings 2014
    DOI

2013

  1. Verifying proofs in constant depth
    Beyersdorff, Olaf, Datta, Samir, Krebs, Andreas, Mahajan, Meena, Scharfenberger-Fabian, Gido,  Sreenivasaiah, Karteek, Thomas, Michael, and Vollmer, Heribert
    ACM Trans. Comput. Theory 2013
    DOI pdf
  2. Small Depth Proof Systems
    Krebs, Andreas, Limaye, Nutan, Mahajan, Meena, and Sreenivasaiah, Karteek
    In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings 2013
    DOI

2012

  1. Counting paths in planar width 2 branching programs
    Mahajan, Meena, Saurabh, Nitin, and Sreenivasaiah, Karteek
    In Eighteenth Computing: The Australasian Theory Symposium, CATS 2012, Melbourne, Australia, January 2012 2012
    DOI pdf
  2. The Complexity of Unary Subset Sum
    Limaye, Nutan, Mahajan, Meena, and Sreenivasaiah, Karteek
    In Computing and Combinatorics - 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings 2012
    DOI pdf
  3. Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs
    Mahajan, Meena, Rao, B. V. Raghavendra, and Sreenivasaiah, Karteek
    In Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings 2012
    DOI

2011

  1. Verifying Proofs in Constant Depth
    Beyersdorff, Olaf, Datta, Samir, Mahajan, Meena, Scharfenberger-Fabian, Gido,  Sreenivasaiah, Karteek, Thomas, Michael, and Vollmer, Heribert
    In Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings 2011
    DOI