Publications

Type All Journal Conference Technical Report
Year All 2026 2025 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007

2026

  1. Journal
    Bounds for packing chromatic number of some subclasses of trees
    K. Mohamed Harith, A. V. Jayanthan, B. V. Raghavendra Rao
    Discuss. Math. Graph Theory, 46(1), pp. 135-176, 2026. DOI
  2. Conference
    On k-Bounded Nondeterminism for Branching Programs and Circuits
    Anselm Haak, Arne Meier, B. V. Raghavendra Rao
    In IPEC, 2026.

2025

  1. Journal
    Algebraic and Combinatorial Algorithms for S-Packing Coloring
    K. Mohamed Harith, A. V. Jayanthan, B. V. Raghavendra Rao
    ACM Commun. Comput. Algebra, 59(1), pp. 1-16, 2025. DOI

2024

  1. Journal
    Proper q-caterpillars are distinguished by their Chromatic Symmetric Functions
    Arunkumar Ganesan, Narayanan Narayanan, B. V. Raghavendra Rao, Sagar S. Sawant
    Discret. Math., 347(12), pp. 114162, 2024. DOI

2023

  1. Journal
    Parameterised Counting in Logspace
    Anselm Haak, Arne Meier, Om Prakash, B. V. Raghavendra Rao
    Algorithmica, 85(10), pp. 2923-2961, 2023. DOI

2022

  1. Journal
    Isomorphism testing of read-once functions and polynomials
    B. V. Raghavendra Rao, Jayalal Sarma
    Inf. Comput., 285(Part), pp. 104921, 2022. DOI

2021

  1. Conference
    Limitations of Sums of Bounded Read Formulas and ABPs
    Purnata Ghosal, B. V. Raghavendra Rao
    In Computer Science - Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28 - July 2, 2021, Proceedings, pp. 147-169, Springer, 2021. DOI
  2. Conference
    Parameterised Counting in Logspace
    Anselm Haak, Arne Meier, Om Prakash, B. V. Raghavendra Rao
    In 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, Saarbrucken, Germany (Virtual Conference), March 16-19, 2021, pp. 40:1-40:17, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2021. DOI

2020

  1. Journal
    Limitations of Sums of Bounded-Read Formulas
    Purnata Ghosal, B. V. Raghavendra Rao
    CoRR, abs/2010.01385, 2020. Link
  2. Journal
    Lower bounds for special cases of syntactic multilinear ABPs
    C. Ramya, B. V. Raghavendra Rao
    Theor. Comput. Sci., 809, pp. 1-20, 2020. DOI
  3. Journal
    On hard instances of non-commutative permanent
    Christian Engels, B. V. Raghavendra Rao
    Discret. Appl. Math., 277, pp. 127-138, 2020. DOI
  4. Conference
    On Measures of Space over Real and Complex Numbers
    Om Prakash, B. V. Raghavendra Rao
    In Computing and Combinatorics - 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29-31, 2020, Proceedings, pp. 508-519, Springer, 2020. DOI
  5. Journal
    On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models
    Purnata Ghosal, B. V. Raghavendra Rao
    Fundam. Informaticae, 177(1), pp. 69-93, 2020. DOI

2019

  1. Journal
    A note on parameterized polynomial identity testing using hitting set generators
    Purnata Ghosal, B. V. Raghavendra Rao
    Inf. Process. Lett., 151, 2019. DOI
  2. Journal
    An upper bound for the regularity of binomial edge ideals of trees
    A. V. Jayanthan, N. Narayanan, B. V. Raghavendra Rao
    J. Algebra Appl., 18(9), pp. 1950170, 7, 2019. DOI
  3. Journal
    Linear projections of the Vandermonde polynomial
    C. Ramya, B. V. Raghavendra Rao
    Theor. Comput. Sci., 795, pp. 165-182, 2019. DOI
  4. Journal
    Lower bounds for multilinear bounded order ABPs
    C. Ramya, B. V. Raghavendra Rao
    CoRR, abs/1901.04377, 2019. Link
  5. Conference
    Lower Bounds for Multilinear Order-Restricted ABPs
    C. Ramya, B. V. Raghavendra Rao
    In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Aachen, Germany, August 26-30, 2019, pp. 52:1-52:14, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2019. DOI
  6. Journal
    Lower bounds for Sum and Sum of Products of Read-once Formulas
    C. Ramya, B. V. Raghavendra Rao
    ACM Trans. Comput. Theory, 11(2), pp. 10:1-10:27, 2019. DOI
  7. Conference
    On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models
    Purnata Ghosal, B. V. Raghavendra Rao
    In Computing and Combinatorics - 25th International Conference, COCOON 2019, Xi'an, China, July 29-31, 2019, Proceedings, pp. 178-192, Springer, 2019. DOI
  8. Journal
    Parameterised Counting Classes with Bounded Nondeterminism
    Anselm Haak, Arne Meier, Om Prakash, B. V. Raghavendra Rao
    CoRR, abs/1904.12156, 2019. Link
  9. Journal
    Regularity of binomial edge ideals of certain block graphs
    A. V. Jayanthan, N. Narayanan, B. V. Raghavendra Rao
    Proc. Indian Acad. Sci. Math. Sci., 129(3), pp. Paper No. 36, 10, 2019. DOI

2018

  1. Conference
    Lower Bounds for Special Cases of Syntactic Multilinear ABPs
    C. Ramya, B. V. Raghavendra Rao
    In Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings, pp. 701-712, Springer, 2018. DOI
  2. Journal
    Lower Bounds for Special Cases of Syntactic Multilinear ABPs
    C. Ramya, B. V. Raghavendra Rao
    CoRR, abs/1804.08810, 2018. Link

2017

  1. Technical Report
    Linear Projections of the Vandermonde Polynomial
    C. Ramya, B. V. Raghavendra Rao
  2. Journal
    Linear Projections of the Vandermonde Polynomial
    C. Ramya, B. V. Raghavendra Rao
    Electron. Colloquium Comput. Complex., TR17, 2017. Link
  3. Conference
    On \textbackslashvarSigma \textbackslashwedge \textbackslashvarSigma \textbackslashwedge \textbackslashvarSigma Circuits: The Role of Middle \textbackslashvarSigma Fan-In, Homogeneity and Bottom Degree
    Christian Engels, B. V. Raghavendra Rao, Karteek Sreenivasaiah
    In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, pp. 230-242, Springer, 2017. DOI
  4. Conference
    On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction
    Purnata Ghosal, Om Prakash, B. V. Raghavendra Rao
    In Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings, pp. 250-261, Springer, 2017. DOI
  5. Conference
    On Weak-Space Complexity over Complex Numbers
    Pushkar S. Joglekar, B. V. Raghavendra Rao, Siddharth S. Sivakumar
    In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, pp. 298-311, Springer, 2017. DOI
  6. Journal
    On Weak-Space Complexity over Complex Numbers
    Pushkar S. Joglekar, B. V. Raghavendra Rao, Siddharth S. Sivakumar
    Electron. Colloquium Comput. Complex., TR17, 2017. Link
  7. Conference
    Testing Polynomial Equivalence by Scaling Matrices
    Markus Blaser, B. V. Raghavendra Rao, Jayalal Sarma
    In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, pp. 111-122, Springer, 2017. DOI

2016

  1. Journal
    Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation
    Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
    Algorithmica, 76(4), pp. 890-909, 2016. DOI
  2. Journal
    Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials
    Christian Engels, B. V. Raghavendra Rao, Karteek Sreenivasaiah
    Electron. Colloquium Comput. Complex., TR16, 2016. Link
  3. Conference
    On Hard Instances of Non-Commutative Permanent
    Christian Engels, B. V. Raghavendra Rao
    In Computing and Combinatorics - 22nd International Conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings, pp. 171-181, Springer, 2016. DOI
  4. Conference
    Sum of Products of Read-Once Formulas
    Ramya C., B. V. Raghavendra Rao
    In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, Chennai, India, December 13-15, 2016, pp. 39:1-39:15, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2016. DOI

2015

  1. Journal
    Building above read-once polynomials: identity testing and hardness of representation
    Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
    Electron. Colloquium Comput. Complex., TR15, 2015. Link
  2. Technical Report
    Limitations of sum of products of Read-Once Polynomials
    C. Ramya, B. V. Raghavendra Rao
  3. Journal
    Limitations of sum of products of Read-Once Polynomials
    C. Ramya, B. V. Raghavendra Rao
    Electron. Colloquium Comput. Complex., TR15, 2015. Link
  4. Conference
    Parameterized Analogues of Probabilistic Computation
    Ankit Chauhan, B. V. Raghavendra Rao
    In Algorithms and Discrete Applied Mathematics - First International Conference, CALDAM 2015, Kanpur, India, February 8-10, 2015. Proceedings, pp. 181-192, Springer, 2015. DOI
  5. Journal
    Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
    Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
    Algorithmica, 73(1), pp. 42-62, 2015. DOI

2014

  1. Conference
    Building above Read-once Polynomials: Identity Testing and Hardness of Representation
    Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
    In Computing and Combinatorics - 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings, pp. 1-12, Springer, 2014. DOI
  2. Journal
    Complexity of Testing Reachability in Matroids
    B. V. Raghavendra Rao, Jayalal Sarma
    Chic. J. Theor. Comput. Sci., 2014, 2014. Link
  3. Journal
    Monomials, multilinearity and identity testing in simple read-restricted circuits
    Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
    Theor. Comput. Sci., 524, pp. 90-102, 2014. DOI
  4. Technical Report
    New Algorithms and Hard Instances for Non-Commutative Computation
    Christian Engels, B. V. Raghavendra Rao
  5. Technical Report
    Parameterized Analogues of Probabilistic Computation
    Ankit Chauhan, B. V. Raghavendra Rao

2013

  1. Conference
    Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems
    Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
    In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, pp. 219-230, Springer, 2013. DOI
  2. Technical Report
    Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
    Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
  3. Journal
    Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits
    Maurice J. Jansen, Meena Mahajan, B. V. Raghavendra Rao
    Comput. Complex., 22(3), pp. 517-564, 2013. DOI
  4. Journal
    Small Space Analogues of Valiant's Classes and the Limitations of Skew Formulas
    Meena Mahajan, B. V. Raghavendra Rao
    Comput. Complex., 22(1), pp. 1-38, 2013. DOI
  5. Journal
    Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
    Markus Blaser, Bodo Manthey, B. V. Raghavendra Rao
    Algorithmica, 66(2), pp. 397-418, 2013. DOI

2012

  1. Conference
    A Probabilistic Analysis of Christofides' Algorithm
    Markus Blaser, Konstantinos Panagiotou, B. V. Raghavendra Rao
    In Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, pp. 225-236, Springer, 2012. DOI
  2. Journal
    Counting classes and the fine structure between NC\(^\mbox1\) and L
    Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
    Theor. Comput. Sci., 417, pp. 36-49, 2012. DOI
  3. Journal
    Faster algorithms for finding and counting subgraphs
    Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, B. V. Raghavendra Rao
    J. Comput. Syst. Sci., 78(3), pp. 698-706, 2012. DOI
  4. Conference
    Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs
    Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
    In Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, pp. 655-667, Springer, 2012. DOI
  5. Conference
    Random Shortest Path Metrics with Applications
    Christian Engels, Bodo Manthey, B. V. Raghavendra Rao
    In 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Munich, Germany, May 29-31, 2012. Extended Abstracts, pp. 121-124, 2012.

2011

  1. Conference
    Isomorphism testing of read-once functions and polynomials
    B. V. Raghavendra Rao, Jayalal Sarma
    In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, Mumbai, India, December 12-14, 2011, pp. 115-126, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2011. DOI
  2. Journal
    On the Complexity of Matroid Isomorphism Problem
    B. V. Raghavendra Rao, Jayalal Sarma
    Theory Comput. Syst., 49(2), pp. 246-272, 2011. DOI
  3. Conference
    Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
    Markus Blaser, Bodo Manthey, B. V. Raghavendra Rao
    In Algorithms and Data Structures - 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings, pp. 110-121, Springer, 2011. DOI

2010

  1. Journal
    Arithmetizing Classes Around NC\textbackslashtextsf\NC\\(^\mbox1\) and L\textbackslashtextsf\L\
    Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao
    Theory Comput. Syst., 46(3), pp. 499-522, 2010. DOI
  2. Conference
    Counting Classes and the Fine Structure between NC\(^\mbox1\) and L
    Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer
    In Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, pp. 306-317, Springer, 2010. DOI
  3. Technical Report
    Counting Classes and the Fine Structure between NC\(^\mbox1\) and L
    Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer

2009

  1. Technical Report
    Faster Algorithms for Finding and Counting Subgraphs
    Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, B. V. Raghavendra Rao, Saket Saurabh
  2. Conference
    On the Complexity of Matroid Isomorphism Problems
    B. V. Raghavendra Rao, Jayalal Sarma
    In Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings, pp. 286-298, Springer, 2009. DOI
  3. Conference
    Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
    Maurice J. Jansen, B. V. Raghavendra Rao
    In Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings, pp. 179-190, Springer, 2009. DOI
  4. Conference
    Small space analogues of Valiant's classes and the limitations of skew formula
    Meena Mahajan, B. V. Raghavendra Rao
    In Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, Germany, 2009. Link
  5. Conference
    Small-Space Analogues of Valiant's Classes
    Meena Mahajan, B. V. Raghavendra Rao
    In Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings, pp. 250-261, Springer, 2009. DOI

2008

  1. Conference
    Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
    Meena Mahajan, B. V. Raghavendra Rao
    In Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, pp. 455-466, Springer, 2008. DOI
  2. Technical Report
    Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae
    Meena Mahajan, B. V. Raghavendra Rao
  3. Technical Report
    On the Complexity of Matroid Isomorphism Problem
    B. V. Raghavendra Rao, Jayalal Sarma

2007

  1. Conference
    Arithmetizing Classes Around NC \(^\mbox1\) and L
    Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao
    In STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, pp. 477-488, Springer, 2007. DOI
  2. Technical Report
    Arithmetizing classes around NC\^1 and L
    Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao