- Proper q-caterpillars are distinguished by their Chromatic Symmetric Functions [pdf]
(with G Arun Kumar, Narayanan N., Sagar S. Sawant)
Appeared in Discrete Mathematics, Vol 347, No.11, pp.114-162, Nov 2024.
- Parameterised Counting in Logspace [pdf]
(with Anselm Haak, Arne Meier, Om Prakash)
Appeared in
Algorithmica, Vol 85, No.10, pp.2923--2961, Oct 2023. A
preliminary version appeared in The 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Mar 2021.
- Isomorphism Testing of Read-once Functions and Polynomials [pdf]
(with Jayalal Sarma)
Appeared in
Information and Computation, Feb 2022. A
preliminary version 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.
- Limitations of Sums of Bounded Read Formulas and ABPs [pdf]
(with Purnata Ghosal)
Appeared in The 16th International Computer Science Symposium in Russia (CSR 2021), Jun 2021.
- On Measures of Space Over Real and Complex numbers [pdf]
(with Om Prakash)
Appeared in The 26th International Conference on Computing and Combinatorics (COCOON 2020), Aug 2020.
- Lower Bounds for Multilinear Order-restricted ABPs [pdf]
(with Ramya C.)
Appeared in 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Sep 2019.
- On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models [pdf]
(with Purnata Ghosal)
Appeared in 25th International Computing and Combinatorics Conference, COCOON 2019, Aug 2019.
- Linear projections of the Vandermonde polynomial [pdf]
(with Ramya C.)
Appeared in TCS, Theoretical Computer Science, Jul 2019.
- Lower bounds for Sum and Sum of Products of Read-once Formulas [pdf]
(with Ramya C.)
- Lower Bounds for Special Classes of Syntactic Multilinear ABPs [pdf]
(with Ramya C.)
Appeared in The 24th International Computing and Combinatorics Conference (COCOON 2018), Jul 2018.
- On Weak-Space Complexity over Complex Numbers [pdf]
(with Pushkar Joglekar, Siddhartha Sivakumar)
Appeared in 21st International Symposium on Fundamentals of Computation Theory (FCT 2017), Sep 2017.
- On depth five Sum-Power-Sum-Power-Sum Circuits: The Role of Middle Σ Fan-in, Homogeneity and Bottom Degree [pdf]
(with Christian Engels, Karteek Sreenivasaiah)
Appeared in 21st International Symposium on Fundamentals of Computation Theory (FCT 2017), Sep 2017.
- Testing Equivalence of Polynomials under Scaling [pdf]
(with Markus Blaser, Jayalal Sarma)
Appeared in 21st International Symposium on Fundamentals of Computation Theory (FCT), Sep 2017.
- On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction [pdf]
(with Purnata Ghosal, Om Prakash)
Appeared in 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), Aug 2017.
- On Hard Instances of Non-Commutative Permanent [pdf]
(with Christian Engels)
Appeared in 22nd International Computing and Combinatorics Conference (COCOON 2016), Aug 2016.
- Parameterized Analogues of Probabilistic Computation [pdf]
(with Ankit Chauhan)
Appeared in Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2015), Feb 2015.
- Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems [pdf]
(with Karl Bringmann, Christian Engels, Bodo Manthey)
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. [pdf]
(with Meena Mahajan, Karteek Sreenivasaiah)
Appeared in The 20th Annual International Computing and Combinatorics Conference COCOON, 4-6 Aug 2014, Atlanta, USA., Aug 2014.
- Complexity of Testing Reachability in Matroids [pdf]
(with Jayalal Sarma)
Appeared in Chicago Journal of Theoretical Computer Science, Vol 2014, No.5, Jul 2014.
- Monomials, multilinearity and identity testing in simple read-restricted circuits [pdf]
(with Meena Mahajan, Karteek Sreenivasaiah)
- Small space analogues of Valiants classes [pdf]
(with Meena Mahajan)
Appeared in
Computational Complexity, Jul 2013. A
preliminary version appeared in Foundations of Computation Theory, FCT, Jul 2009.
- Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals [pdf]
(with Markus Blaeser, Bodo Manthey)
Appeared in
Algorithmica, Vol 66, No.2, pp.397-418, Jul 2013. A
preliminary version appeared in WADS Symposium, Jul 2011.
- Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits [pdf]
(with Maurice Jansen, Meena Mahajan)
- Probabilistic Analysis of Christofides Algorithm. [pdf]
(with Markus Blaeser, Konstantinos Panagiotou)
Appeared in Scandinavian Symposium on Algorithm Theory (SWAT), SWAT, Jul 2012.
- Faster Algorithms for Finding and Counting Subgraphs. [pdf]
(with Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh)
Appeared in Journal of Computer and System Sciences, Vol 78, pp.698-706, Jul 2012.
- Counting classes and the fine structure between NC^1 and L [pdf]
(with Samir Datta, Meena Mahajan, Michael Thomas, Heribert Vollmer)
- On the Complexity of Matroid Isomorphism Problem [pdf]
(with 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 [pdf]
(with Meena Mahajan, Nutan Limaye)
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 [pdf]
(with Maurice Jansen)
Appeared in Symposium on Computer Science in Russia (CSR), CSR, Jul 2009.