Research Publications/ReportsListing last 25 publications. (View All) View/Hide Filter
- Lower Bounds for Special Classes of Syntactic Multilinear ABPs
- On Weak-Space Complexity over Complex Numbers
- On depth five Sum-Power-Sum-Power-Sum Circuits: The Role of Middle Σ Fan-in, Homogeneity and Bottom Degree
- Testing Equivalence of Polynomials under Scaling
- On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction
- Sum of products of Read-Once Polynomials
- On Hard Instances of Non-Commutative Permanent
- Parameterized Analogues of Probabilistic Computation
- Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
Karl Bringmann, Christian Engels, Bodo Manthey, Raghavendra Rao B V, Appeared in Algorithmica, (To Appear), Dec 2014. A preliminary version appeared in 38th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2013.
- Building above read-once polynomials: identity testing and hardness of representation.
- Complexity of Testing Reachability in Matroids
- Monomials, multilinearity and identity testing in simple read-restricted circuits
Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah, Appeared in Theoretical Computer Science, 2014. A preliminary version under the title "Monomials in read once/twice formulas and branching programs" appeared in Mathematical Foundations of Computer Science (MFCS), 2012.
- Small space analogues of Valiants classes
- Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
- Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits
Maurice Jansen, Meena Mahajan, Raghavendra Rao B V, Appeared in Computational Complexity, Jul 2013. A preliminary version under the title "Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae" appeared in Mathematical Foundations of Computer Science (MFCS), MFCS, Jul 2008.
- Probabilistic Analysis of Christofides Algorithm.
- Faster Algorithms for Finding and Counting Subgraphs.
- Counting classes and the fine structure between NC^1 and L
Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer, Appeared in Theoretical Computer Science, TCS, Vol 417, pp.36-49, Jul 2012. A preliminary version under the title "Counting Classes and the Fine Structure between NC^1 and L" appeared in Mathematical Foundations of Computer Science (MFCS), MFCS, Jul 2010.
- Isomorphism Testing of Read-once Functions and Polynomials
Raghavendra Rao B V, Jayalal Sarma, Appeared in Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), LIPIcs–Leibniz International Proceedings in Informatics, Vol 13, pp.115-126, Dec 2011.
- On the Complexity of Matroid Isomorphism Problem
Raghavendra Rao B V, Jayalal Sarma, Appeared in Theory of Computing Systems, Vol 49, No.2, pp.246-272, Aug 2011. A preliminary version appeared in Proceedings of the 4th Computer Science Symposium in Russia (CSR 2009), Vol 5675, pp.286-298, Aug 2009.
- Arithmetizing Classes around NC1 and L
Meena Mahajan, Nutan Limaye, Raghavendra Rao B V, Appeared in Theory of Computing Systems, Vol 46, No.3, pp.499-522, Jul 2010. A preliminary version appeared in Symposium on Theoretical Aspects of Computer Science, STACS, Mar 2007.
- Simulation of Arithmetical Circuits by Branching Programs Preserving Constant Width and Syntactic Multilinearity