Talks & Seminars
Title: Matching under preferences: Stability is ubiquitous but popularity is hard to find
Dr. Sushmita Gupta, University of Bergen
Date & Time: January 29, 2019 11:35
Venue: Dept. of CSE, Room No. 109, 01st Floor, New CSE/CC Bldg.
Matching under preferences is a research area that finds numerous applications in practice as diverse as assigning students to colleges, workers to firms, kidney donors to recipients, users to servers in a distributed internet service, to just name a few. Indeed this topic is at the heart of the intersection between Computer Science and Economics, and has been recognized as such by a Nobel prize in Economics. In the first part of the talk, I will discuss canonical problems in this area, namely, stable matching and its generalization, popular matching. In the second part of the talk, I will present a new result published in SODA'19 that resolved the arguably main open problem in the subarea of popular matching: In an arbitrary graph, deciding if a popular matching exists is NP-complete. The computational complexity of this problem had been unknown for over a decade, during which it was repeatedly posed as a fundamental open question. We will conclude the talk by discussing my future research plans and teaching interests.
Speaker Profile:
I am currently a researcher at the University of Bergen, Norway. Prior to this, I was a postdoctoral researcher at the University of Kyoto. I got my bachelor's, master's and doctoral degrees from Chennai Mathematical Institute, Simon Fraser University and the University of Southern Denmark, respectively.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback