Currently I am a postdoctoral research fellow at the University of Bergen, Institute for Informatics. My host is Prof. Petter E. Bjørstad. Prior to this, between January 2014-March 2015, I was a postdoctoral research fellow in University of Kyoto, Algorithms and Complexity Theory group, hosted by Prof. Kazuo Iwama. I received b PhD degree from the University of Southern Denmark, where my advisers were Prof. Joan Boyar and Kim S. Larsen. I obtained a MS degree from Simon Fraser University, under the supervision of Prof. Valentine Kabanets.

My Google Scholar profile is here

Publications

Survey

Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Some Hard Stable Marriage Problems: A Survey on Multivariate Analysis

Published Articles

Sushmita Gupta, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Popular Matching in Roommates Setting is NP-hard.

Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Gehrlein Stability in Committee Selection: Parameterized Hardness and Algorithms

  • Accepted to International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019.

Akanksha Agrawal, Sushmita Gupta, Pallavi Jain and R. Krithika. Quadratic Vertex Kernel for Split Vertex Deletion.

  • Accepted to 11th International Conference on Algorithms and Complexity (CIAC), 2019.

Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. When Rigging a Tournament, Let Greediness Blind You.

Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Winning a Tournament by Any Means Necessary.

Sushmita Gupta, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Stability in Barter Exchange Markets.

  • In the proc. of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.

Sushmita Gupta, Sanjukta Roy. Stable Matching Games: Manipulation via Subgraph Isomorphism.

Deeksha Adil, Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Parameterized Algorithms for the Stable Matching Problem with Ties and Incomplete Lists.

  • Theoretical Computer Science, 723:1-10, 2018.

Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Parameterized Algorithms and Kernels for Rainbow Matching.

  • Accepted to Algorithmica. Available on request.
  • Preliminary version appeared in the proc. of the International Symposium on Mathematical Foundations of Computer Science (MFCS), 71:1--71:13, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.71

Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Parameterized Analysis for Graph Group Activity Selection Problem

Sushmita Gupta, Kazuo Iwama and Shuichi Miyazaki. Total Stability in Stable Matching Games.

Sushmita Gupta, Shahin Kamali and Alejandro Lopez-Ortiz. On the Advice Complexity of the k-Server Problem under Sparse Metrics.

Akanksha Agrawal, Sushmita Gupta, Saket Saurabh and Roohani Sharma. Improved Algorithms for Independent Feedback Vertex Set.

Joan Boyar, Sushmita Gupta and Kim Skak Larsen. Relative Interval Analysis of Paging Algorithms on Access Graphs.

Sushmita Gupta, Venkatesh Raman and Saket Saurabh. Maximum r-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds.

  • SIAM Journal of Discrete Mathematics, 26(4):1758--1780, 2012. https://doi.org/10.1137/09077850X
  • A preliminary version of this paper, titled "Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems", appeared in the proc. of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Springer LNCS, 4337:139--151, 2006.

Joan Boyar, Sushmita Gupta and Kim Skak Larsen. Access Graph Results for LRU versus FIFO under Relative Worst Order Analysis.

Sushmita Gupta. Feedback Arc Set Problem in Bipartite Tournament.

  • Information Processing Letters (IPL) 105(4):150-154, 2008. https://doi.org/10.1016/j.ipl.2007.08.023
  • A preliminary version of this paper appeared in the proc. of the Conference on Theory and Applications of Models of Computation (TAMC), Springer LNCS 4484: 354--361, 2007

Current Work

Sushmita Gupta, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Popular Matching in Roommates Setting is NP-hard

Sushmita Gupta, Saket Saurabh and Meirav Zehavi. On Treewidth and Stable Marriage.

Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Balanced Stable Marriage: How Close is Close Enough ?

Education

Doctorate: PhD in Computer Science, University of Southern Denmark, Denmark

  • Defended in November 2013
  • Thesis entitled "New perspectives on paging and server problems"
  • Advisors: Professor Joan Boyar and Professor Kim Skak Larsen

Masters: M. Sc in Computer Science, Simon Fraser University, Canada

  • Completed in May 2007
  • Thesis entitled "Hardness amplification in nondeterministic logarithmic space"
  • Advisor: Professor Valentine Kabanets.

Masters: M. Sc. in Computer Science, University of Pennsylvania, USA.

  • Completed May 2010.

Bachelors: B. Sc. (Honours) in Mathematics, Chennai Mathematical Institute, India.

  • Completed July 2005.

Employment

2015 - current: Postdoctoral Fellow, Institute for Informatics, University of Bergen

2014 - 2015: Postdoctoral Fellow, Iwama Lab, Kyoto University

Teaching

Teaching assistant for the following courses.

University of Southern Denmark

2013 Spring -- Linear and integer programming

2012 Fall -- Algorithms and probability

2011 Fall -- Combinatorics, probability and randomized algorithms

University of Pennsylvania

2010 -- Graduate course in Theory of Computation.

2009 -- Mathematical foundations of computer science

Simon Fraser University

2006, Spring -- Discrete mathematics

2006, Fall -- Introduction to programming II, Java programming

2005 -- Data structures and algorithm