Research Publications/Reports
Listing last 25 publications. (View All) View/Hide Filter- Energy and Output Patterns in Boolean Circuits
Jayalal Sarma, Kei Uchizawa, Appeared in 18th Annual Conference on Theory and Applications of Models of Computation (TAMC 2024), May 2024.
- On Rotation Distance of Rank Bounded Trees
Anoop S K M, Jayalal Sarma, Appeared in Fundamentae Informatica, Mar 2024. A preliminary version under the title "On Rotation Distance, Transpositions and Rank Bounded Trees" appeared in 28th International Computing and Combinatorics Conference (COCOON 2022), Oct 2022.
- On Separating Words Problem over Groups
Neha Kuntewar, Anoop S K M, Jayalal Sarma, Appeared in 25th International Conference on Descriptional Complexity of Formal Systems (DCFS 2023), Jul 2023.
- Isomorphism Testing of Read-once Functions and Polynomials
Raghavendra Rao B V, 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.
- On Alternation, VC-dimension and k-fold Union of Sets
Amit Kumar Roy, Jayalal Sarma, Appeared in European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB 2021), Jul 2021.
- On the Computational Power of Programs over BA_2 Monoid
Manasi Kulkarni, Jayalal Sarma, Janani Sundaresan, Appeared in 14th-15th International Conference on Language and Automata Theory and Applications (LATA 2021), Mar 2021.
- New Bounds for Energy Complexity of Boolean Functions
Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma, Appeared in Theoretical Computer Science, Sep 2020. A preliminary version appeared in The 24th International Computing and Combinatorics Conference (COCOON 2018), Jul 2018.
- Power of Decision Trees with Monotone Queries
Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma, Appeared in The 26th International Conference on Computing and Combinatorics (COCOON 2020), Aug 2020.
- On the Mystery of Negations in Circuits : Structure vs Power
Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma, Appeared in The 26th International Conference on Computing and Combinatorics (COCOON 2020), Aug 2020.
- Sensitivity, Affine Transforms and Quantum Communication Complexity
Krishnamoorthy Dinesh, Jayalal Sarma, Appeared in Theoretical Computer Science (Invited Special Issue), Jun 2020. A preliminary version appeared in 25th International Computing and Combinatorics Conference (COCOON 2019), Vol 2018, No.152, Aug 2019.
- On Pure Space vs Catalytic Space
Sagar Bisoyi, Krishnamoorthy Dinesh, Jayalal Sarma, Appeared in The 16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020), Apr 2020.
- Space Complexity of Labelled Graph Reachability Problem
Vidhya Ramaswamy, Jayalal Sarma, K.S. Sunil, Appeared in Journal of Computer and System Sciences, Jun 2019. A preliminary version appeared in 11th International Conference on Language and Automata Theory and Applications (LATA 2017), Mar 2017.
- 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.
- 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.
- 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.
- Depth Lower Bounds against Circuits with Sparse Orientation
Sajin Koroth, Jayalal Sarma, Appeared in Fundamenta Informaticae, Vol 152, No.2, pp.123-144, Apr 2017. A preliminary version under the title "Depth Lower bounds against Circuits with Sparse Orientation" 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.
- 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.
- 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.