BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computer Science and Engineering
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250806T120000
DTEND;TZID=Asia/Kolkata:20250806T130000
DTSTAMP:20260923T224045
CREATED:20250730T061826Z
LAST-MODIFIED:20250730T165814Z
UID:1727-1754481600-1754485200@homecse.iitd.ac.in
SUMMARY:Rank Aggregation and Fairness by Diptarka Chakraborty
DESCRIPTION:Abstract: Aggregating multiple input rankings over a set of candidates to generate a consensus ranking is one of the fundamental ranking problems\, having many applications in social choice theory\, hiring\, college admission\, web search\, and databases. However\, the optimal consensus ranking might be biased against any individual candidate or candidates belonging to certain marginalized communities or groups. This has motivated studies of the rank aggregation problem from the fairness perspective. While finding a consensus ranking\, the additional objective is to ensure fair representation of each group in the top positions of the final aggregated ranking. In this talk\, we will discuss various algorithms to find such a fair ranking approximately.\n\nSpeaker: Diptarka Chakraborty is an Assistant Professor at the National University of Singapore. He did his Ph.D. at the Indian Institute of Technology\, Kanpur. Before joining NUS\, he spent two years at Charles University\, Prague\, and then almost a year at Weizmann Institute of Science\, Israel\, as a post-doctoral fellow. His research interest mostly lies in theoretical computer science\, more specifically\, algorithms on large data sets\, approximation algorithms\, sublinear algorithms\, string matching algorithms\, and graph algorithms. He is a recipient of the best paper award at FOCS 2018 and the Google South & Southeast Asia Research Award 2022.
URL:https://homecse.iitd.ac.in/event/rank-aggregation-and-fairness/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250822T140000
DTEND;TZID=Asia/Kolkata:20250822T150000
DTSTAMP:20260923T224045
CREATED:20250827T082004Z
LAST-MODIFIED:20250827T082004Z
UID:1825-1755871200-1755874800@homecse.iitd.ac.in
SUMMARY:Optimal Capacity Modification for Stable Matchings with Ties by Dr. Keshav Ranjan
DESCRIPTION:Abstract: In this talk\, we consider the Hospitals/Residents (HR) problem in the presence of ties in preference lists of hospitals. Among the three notions of stability\, viz. weak\, strong\, and super stability\, we focus on strong stability. Strong stability is appealing both theoretically and practically; however\, its existence is not guaranteed. Our objective is to optimally increase hospitals’ quotas so that the resulting instance admits a strongly stable matching.\nSuch an augmentation is guaranteed to exist when resident preference lists are strict. We explore two natural optimization criteria:\n\n\n\nMINSUM: minimizing the total capacity increase across all hospitals and \nMINMAX: minimizing the maximum capacity increase for any hospital\n\nWe prove that the MINSUM problem admits a polynomial-time algorithm\, whereas the MINMAX problem is NP-hard. We prove an analogue of the Rural Hospitals theorem for the MINSUM problem. When each hospital incurs a cost for a unit increase in its quota\, the MINSUM problem becomes NP-hard\, even for 0/1 costs. In fact\, we show that the problem cannot be approximated to any multiplicative factor. We also present a polynomial-time algorithm for optimal MINSUM augmentation when a specified subset of edges is required to be included in the matching.\n\nThe talk is based on a recent work accepted at IJCAI 2025 and is a joint work with Meghana Nasre (IIT-M) and Prajakta Nimbhorkar (CMI). \nBio: Keshav Ranjan recently (July 2025) completed his Ph.D. from the Department of Computer Science and Engineering\, IIT Madras\, under the supervision of Dr. Meghana Nasre. His Doctoral thesis\, titled “Two-Sided Matchings: Lower Quotas\, Ties\, and Capacity Augmentation”\, focuses on the algorithmic aspects of two-sided matching problems under various constraints. Previously\, he held an M. Tech degree in Mathematics and Computing from the Department of Mathematics\, IIT Patna. His research interests lie in the broad area of Graph Algorithms\, with a particular focus on matching problems with preferences.
URL:https://homecse.iitd.ac.in/event/optimal-capacity-modification-for-stable-matchings-with-ties-by-dr-keshav-ranjan/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR