Research Publications/Reports
Listing last 25 publications. (View All) View/Hide Filter- Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco dAmore, Francois Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Vaclav Rozhon, Jukka Suomela, To Appear in 57th Annual ACM Symposium on Theory of Computing (STOC), Vol , No., Jun 2025.
- Almost-catalytic Computation
Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Deep Rai, Jayalal Sarma, To Appear in 14th International Conference on Algorithms and Complexity (CIAC 2025), Vol , No., Jun 2025.
- Range Avoidance in Boolean Circuits via Turan-type Bounds
Neha Kuntewar, Jayalal Sarma, Appeared in Electronic Collquium of Computational Complexity, Vol , No.2005-24, Mar 2025.
- Parameterized Saga of First-Fit and Last-Fit Coloring
Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Shaily Verma, Appeared in 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), Vol , No., Mar 2025.
- A Simple Algorithm for Consistent Query Answering under Primary KeysArticle
Diego Figueira, Anantha Padmanabha, Luc Segoufin, ENS-Pari, Cristina Sirangelo, Appeared in Logical Methods in Computer Science, Vol 21, No.1, Feb 2025.
- A (3+epsilon) -Approximate Correlation Clustering Algorithm in Dynamic Streams
Mélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, Jerra Uitto, Appeared in TheoretiCS, Vol 4, No., Feb 2025.
- Tolerant Testing and Distance Estimation for Distributions Under Memory Constraints
Sampriti Roy, Yadu Vasudev, Appeared in International Conference on Current Trends in. Theory and Practice of Computer Science (SOFSEM 2025), Vol , No., Feb 2025.
- Faster Set Cover in the MPC Model
Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju, Joshua Sobel, Appeared in Proceedings of the 26th International Conference on Distributed Computing and Networking (ICDCN 2025), Vol , No., Jan 2025.
- Hazard-free Decision Trees
Deepu Benson, Balagopal Komarath, Sai Soumya Nalli, Jayalal Sarma, Appeared in (Manuscript), Vol , No., Dec 2024.
- Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions
Diego Figueira, CNRS, Bordeaux, S. Krishna, Om Swostik Mishra, Anantha Padmanabha, Appeared in 21st International Conference on Principles of Knowledge Representation and Reasoning, Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, Vol , No., Nov 2024.
- Proper q-caterpillars are distinguished by their Chromatic Symmetric Functions
G Arun Kumar, Narayanan N., Raghavendra Rao B V, Sagar S. Sawant, Appeared in Discrete Mathematics, Vol 347, No.11, pp.114-162, Nov 2024.
- Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), Vol 294, No.4, pp.1-16, Jun 2024.
- 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.
- Succinct Data Structure for Graphs with d-Dimensional t-Representation
Girish Balakrishnan, Sankardeep Chakraborty, Seungbum Jo, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Data Compression Conference (DCC 2024), pp.546, Mar 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.
- A faster algorithm for Vertex Cover parameterized by solution size
David Harris, Narayanaswamy N S, Appeared in 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), Mar 2024.
- Succinct Data Structure for Path Graphs
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Information and Computation, Vol 105124, Jan 2024. A preliminary version appeared in Data Compression Conference (DCC 2022), Mar 2022.
- Approximately interpolating between uniformly and non-uniformly polynomial kernels
Akanksha Agrawal, Ramanujan M S, Appeared in 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2023.
- Parameterised Counting in Logspace
Anselm Haak, Arne Meier, Om Prakash, Raghavendra Rao B V, 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.
- Recognizing Well-Dominated Graphs is NP-complete
Akanksha Agrawal, Henning Fernau, Mann Kevin, Philipp Kindermann, Uéverton S. Souza, Appeared in Information Processing Letters, Oct 2023.
- Testing properties of distributions in the streaming model
Sampriti Roy, Yadu Vasudev, Appeared in 34th International Symposium on Algorithms and Computation (ISAAC 2023), Sep 2023.
- Matchings under One-Sided Preferences with Soft Quotas
Santhini K A, Meghana Nasre, Raghu Raman Ravi, Appeared in International Joint Conference on Artificial Intelligence (IJCAI), Aug 2023.
- 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.
- Optimal Cost based allocation under Two sided preferences
Girija Limaye, Meghana Nasre, Appeared in International Workshop on Combinatorial Algorithms (IWOCA), pp.259--270, Jun 2023.
- Critical Relaxed Stable Matchings with Two-Sided Ties
Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar, Appeared in 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023.