Research Publications/ReportsListing last 25 publications. (View All) View/Hide Filter
- Reusable Garbled Deterministic Finite Automata from Learning With Errors
- Popularity in the generalized Hospital Residents setting
- Comparator Circuits over Finite Bounded Posets
Balagopal Komarath, Jayalal Sarma, Sunil K.S., Appeared in Information & Computation, (Accepted), Apr 2017. A preliminary version appeared in Proceedings of International Conference on Automata, Languages and Programming (ICALP), Jul 2015.
- Min/Max-Poly Weighting Schemes and the NL vs UL Problem
Anant Dhayal, Jayalal Sarma, Saurabh Sawlani, Appeared in ACM Transactions on Computation Theory (Accepted), Mar 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
- Sum of products of Read-Once Polynomials
- Characterization and Lower Bounds for Branching Program Size using Projective Dimension
- Information Spreading in Dynamic Networks under Oblivious Adversaries
- Hitting Set for hypergraphs of low VC-dimension
- A Refined Analysis of Online Path Coloring in Trees
- On the Sensitivity Conjecture for Read-k Formulas
- On the Complexity Landscape of Connected f-factor Problems
- On Hard Instances of Non-Commutative Permanent
- Sub-families of Baxter Permutations Based on Pattern Avoidance
- Pebbling Meets Coloring: Reversible Pebble Game On Trees
Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani, Appeared in Computing Research Repository, arXiv:1604.05510, Apr 2016.under the title "Reversible Pebble Game on Trees" appeared in 21st International Computing and Combinatorics Conference (COCOON 2015), Aug 2015.
- 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.
- Distributed Algorithmic Foundations of Dynamic Networks
- 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.
- Balanced Allocation: Patience is not a virtue
- Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks
- Minimax regret 1-sink location problem in dynamic path networks
John Augustine, Yuya Higashikawa, Siu-Wing Cheng, Mordecai J. Golin, Naoki Katoh, Guanqun Ni, Bing Su, Yin-Feng Xu, Appeared in Theoretical Computer Science, . Comput. Sci. 588: 24-36 (2015) 2013, Vol 588, No.2013, pp.24-36, Jul 2015.
- Approximation and Exact Algorithms for special cases of Connected f-Factors
- Block Sorting is APX-Hard
- Enforcing Efficient Equilibria in Network Design Games via Subsidies
John Augustine, Ioannis Caragiannis, Angelo Fanelli, Christos Kalaitzis, Appeared in Algorithmica, Vol 72, No.1, pp.44--82, May 2015. A preliminary version under the title "Enforcing efﬁcient equilibria in cost sharing games via subsidies" appeared in Proceedings of the Symposium on Parallelism in Algorithms and Architectures (2012), Jun 2012.
- Distributed agreement in dynamic peer-to-peer networks