Theory Group

Recent News

• Shreyas Pais Paper wins Best Paper Award at ICDCN 2025

• Nalli Sai Soumya is a co-winner of the Best BTP award at CSE Dept.

• Anantha Padmanabha joins the theory group

• Shreyas Pai joins the theory group

• FDP on Core CS Theory

• Online Locality Meets Distributed Quantum Computing

  Authors: 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
  57th Annual ACM Symposium on Theory of Computing (STOC), Vol , No., Jun 2025

• Parameterized Saga of First-Fit and Last-Fit Coloring

  Authors: Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Shaily Verma
  42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), Vol , No., Mar 2025

• Tolerant Testing and Distance Estimation for Distributions Under Memory Constraints

  Authors: Sampriti Roy, Yadu Vasudev
  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

  Authors: Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju, Joshua Sobel
  Proceedings of the 26th International Conference on Distributed Computing and Networking (ICDCN 2025), Vol , No., Jan 2025

• Proper q-caterpillars are distinguished by their Chromatic Symmetric Functions

  Authors: G Arun Kumar, Narayanan N., Raghavendra Rao B V, Sagar S. Sawant
  Discrete Mathematics, Vol 347, No.11, pp.114-162, Nov 2024

• A faster algorithm for Vertex Cover parameterized by solution size

  Authors: David Harris, Narayanaswamy N S
  41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), Mar 2024

• On Rotation Distance of Rank Bounded Trees

  Authors: Anoop S K M, Jayalal Sarma
  Fundamentae Informatica, Mar 2024

• Approximately interpolating between uniformly and non-uniformly polynomial kernels

  Authors: Akanksha Agrawal, Ramanujan M S
  43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2023

• Recognizing Well-Dominated Graphs is NP-complete

  Authors: Akanksha Agrawal, Henning Fernau, Mann Kevin, Philipp Kindermann, Uéverton S. Souza
  Information Processing Letters, Oct 2023

• Testing properties of distributions in the streaming model

  Authors: Sampriti Roy, Yadu Vasudev
  34th International Symposium on Algorithms and Computation (ISAAC 2023), Sep 2023