Reported Research Outcomes

(in reverse chronological order).
papers in the area

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.
Parameterised Counting in Logspace [pdf]
(with Anselm Haak, Arne Meier, Om Prakash)

Appeared in The 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Mar 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.)

Appeared in ToCT, ACM Transactions on Computation Theory, Vol 11, No.2, pp.10:1-10:27, May 2019. A preliminary version under the title "Sum of products of Read-Once Polynomials" appeared in 36th International Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2016.
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)

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

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

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

Last updated on Fri Jul 25 10:15:59 IST 2014