Theory Group

Recent News

• Narayanaswamy awarded the Best Teacher award (2023) in the CSE Dept

• Alan Joel wins the best BTP award for 2023.

• Girija Limaye defended her Ph.D. thesis.

• Om Prakash defended his PhD thesis.

• FSTTCS 2022 at IIT Madras during Dec 15-20

• 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

• Matchings under One-Sided Preferences with Soft Quotas

  Authors: Santhini K A, Meghana Nasre, Raghu Raman Ravi
  International Joint Conference on Artificial Intelligence (IJCAI), Aug 2023

• Optimal Cost based allocation under Two sided preferences

  Authors: Girija Limaye, Meghana Nasre
  International Workshop on Combinatorial Algorithms (IWOCA), pp.259--270, Jun 2023

• Erdős-Pósa property of obstructions to interval graphs

  Authors: Akanksha Agrawal, Daniel Lkoshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi
  Journal of Graph Theory, Vol 102, No.4, pp.702-727, Apr 2023

• Clustering What Matters: Optimal Approximation for Clustering with Outliers

  Authors: Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, Jie Xue
  The 37th AAAI Conference On Artificial Intelligence, Feb 2023

• Computing Square Colorings on Bounded-Treewidth and Planar Graphs

  Authors: Akanksha Agrawal, Daniel Marx, Daniel Neuen, Jasper Slusallek
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Jan 2023

• Trade-Offs in Dynamic Coloring for Bipartite and General Graphs

  Authors: Manas Jyothi Kashyap, Narayanaswamy N S, Meghana Nasre, Sai Mohith Potluri
  Algorithmica, Vol 85, No.4, pp.854--878, Jan 2023

• Envy-freeness and relaxed stability: hardness and approximation algorithms

  Authors: Prem Krishnaa, Girija Limaye, Meghana Nasre, Prajakta Nimbhorkar
  Journal of Combinatorial Optimization, Vol 45, No.1, pp.41, Jan 2023