#### Research Publications/Reports

Listing last 25 publications. (View All) View/Hide Filter**Characterization and Lower Bounds for Branching Program Size using Projective Dimension**Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma, Appeared in

*ACM Transactions on Computation Theory*, Vol 11, No.8, Mar 2019. A preliminary version appeared in 36th International Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2016.**Alternation, Sparsity and Sensitivity : Combinatorial Bounds and Exponential Gaps**Krishnamoorthy Dinesh, Jayalal Sarma, Appeared in

*Theoretical Computer Science*, Mar 2019. A preliminary version appeared in 4th Annual Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2018), Feb 2018.**Sensitivity, Affine Transforms and Quantum Communication Complexity**Krishnamoorthy Dinesh, Jayalal Sarma, Appeared in

*Electronic Colloquium of Computational Complexity*, Technical Report, Vol 2018, No.152, Aug 2018.**Comparator Circuits over Finite Bounded Posets**Balagopal Komarath, Jayalal Sarma, Sunil K.S., Appeared in

*Information & Computation*, (Special Issue for Selected Papers from ICALP 2015), Vol 261, No.2, pp.160-174, Aug 2018. A preliminary version appeared in Proceedings of International Conference on Automata, Languages and Programming (ICALP), Jul 2015.**New Bounds for Energy Complexity of Boolean Functions**Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma, Appeared in

*The 24th International Computing and Combinatorics Conference (COCOON 2018)*, Jul 2018.**Pebbling Meets Coloring: Reversible Pebble Game On Trees**Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani, Appeared in

*Journal of Computer and System Sciences*, Vol 91, pp.33-41, Feb 2018. A preliminary version under the title "Reversible Pebble Game on Trees" appeared in 21st International Computing and Combinatorics Conference (COCOON 2015), Aug 2015.**Testing Equivalence of Polynomials under Scaling**Markus Blaser, Raghavendra Rao B V, Jayalal Sarma, Appeared in

*21st International Symposium on Fundamentals of Computation Theory (FCT)*, Sep 2017.**Min/Max-Poly Weighting Schemes and the NL vs UL Problem**Anant Dhayal, Jayalal Sarma, Saurabh Sawlani, Appeared in

*ACM Transactions on Computation Theory*, Vol 9, No.10, May 2017. A preliminary version under the title "Polynomial Min/Max-weighted Reachability is in Unambiguous Logspace" appeared in Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014), Dec 2014.**Space Complexity of Labelled Graph Reachability Problem**Vidhya Ramaswamy, Jayalal Sarma, K.S. Sunil, Appeared in

*11th International Conference on Language and Automata Theory and Applications (LATA 2017)*, Mar 2017.**Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices**Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma, Appeared in

*ACM Transactions on Computation Theory (To Appear)*, Apr 2016. A preliminary version under the title "Arithmetic Circuit Lower Bounds via MaxRank" appeared in 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Lecture Notes in Computer Science, Vol 7965, pp.661-672, Jul 2013.**On the Complexity of L-reachability**Balagopal Komarath, Jayalal Sarma, K.S. Sunil, Appeared in

*Fundamenta Informaticae*, Mar 2016. A preliminary version appeared in 16th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2014), Lecture Notes in Computer Science, Vol 8614, pp.258-269, Aug 2014.**Pebbling, Entropy and Branching Program Size Lower Bounds**Balagopal Komarath, Jayalal Sarma, Appeared in

*ACM Transactions on Computation Theory*, Dec 2014. A preliminary version appeared in 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Leibniz International Proceedings in Informatics, Vol 20, pp.622-633, Feb 2013.**Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth**Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum, Navid Talebanfard, Appeared in

*39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014)*, Lecture Notes in Computer Science, Vol 8634, pp.336-347, Aug 2014.**Depth Lower bounds against Circuits with Sparse Orientation**Sajin Koroth, Jayalal Sarma, Appeared in

*Proceedings of the 20th International Computing and Combinatorics Conference (COCOON 2014)*, Lecture Notes in Computer Science, Vol 8591, pp.596-607, Aug 2014.**Complexity of Testing Reachability in Matroids**Raghavendra Rao B V, Jayalal Sarma, Appeared in

*Chicago Journal of Theoretical Computer Science*, Vol 2014, No.5, Jul 2014.**Balancing Bounded Treewidth Circuits**Maurice Jansen, Jayalal Sarma, Appeared in

*Theory of Computing Systems*, Vol 54, No.2, pp.318-336, Jan 2014. A preliminary version appeared in 5th International Computer Science Symposium in Russia (CSR 2010), Vol 6072, pp.228-239, Jun 2010.**On Directed Tree Realizations of Degree Sets**Prasun Kumar, Jayalal Sarma, Saurabh Sawlani, Appeared in

*Accepted to International Workshop on Algorithms and Computations (WALCOM 2013)*, Lecture Notes in Computer Science, Vol 7748, pp.274--285, Feb 2013.**Using Elimination Theory to Construct Rigid Matrices**Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma, Appeared in

*Computational Complexity (accepted)*, Jul 2012. A preliminary version under the title "Using Elimination Theory to construct Rigid Matrices" appeared in Proceedings of Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), Vol 4, pp.299-310, Dec 2009.**On Isomorphism Testing of Groups with Normal Hall Subgroups**Youming Qiao, Jayalal Sarma, Bangsheng Tang, Appeared in

*Journal of Computer Science and Technology (JCST)*, Special Issue on Theoretical Computer Science (by invitation), Vol 27, No.4, pp.687-701, Jul 2012. A preliminary version appeared in Proceedings of 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Vol 9, pp.567-578, Mar 2011.**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.**Deterministic BlackBox Identity Testing Pi-ordered Algebraic Branching Programs**Maurice Jansen, Youming Qiao, Jayalal Sarma, Appeared in

*Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)*, Vol 8, pp.296-307, Dec 2010.**Limiting Negations in Bounded Treewidth and Upward Planar Circuits**Jing He, Hongyu Liang, Jayalal Sarma, Appeared in

*35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010)*, Lecture Notes in Computer Science, Vol 6281, pp.417-428, Aug 2010.**Deterministic Polynomial Identity Testing of Read-once Algebraic Branching Programs**Maurice Jansen, Youming Qiao, Jayalal Sarma, Appeared in

*Manuscript*, Jun 2010.**On the Complexity of Rank and Rigidity**Meena Mahajan, Jayalal Sarma, Appeared in

*Theory of Computing Systems*, Special issue (by invitation), Vol 46, No.1, pp.9--26, Jan 2010. A preliminary version appeared in Proceedings of the 2nd International Computer Science Symposium in Russia (CSR 2007), Vol 4649, pp.269--280, Aug 2007.