BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T121604Z
UID:Seminar-pizza-1342@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Qiyi Tang:MAILTO:Qiyi.Tang@liverpool.ac.uk
DTSTART:20250502T130000
DTEND:20250502T140000
SUMMARY:Friday Lunch and Talk Series
DESCRIPTION:Will Rosenbaum: A Quadratic Lower Bound for Stable Roommates Solvability\n\nThe Stable Marriage Problem (SM) considers two disjoint sets of agents where the agents of each set rank the agents of the other set. The goal is to find a matching between the sets that is stable in the sense that no pair of agents prefer one another to their assigned partners. In a seminal work, Gusfield and Irving showed that stable matchings always exist and devised an efficient algorithm for finding one.\n\n\n\nWe consider a variant of SM known as the Stable Roommates Problem (SR) in which there is only one set of agents and each agent ranks all other agents in the set. Unlike SM, an SR instance may not admit a stable matching. In 1987, Irving devised an algorithm that finds a stable matching or reports that none exists in time $O(n^2)$ for instances with $n$ agents. In this talk, we will show that any algorithm that decides SR solvability---the task of deciding if given preferences admit a stable matching---requires $\Omega(n^2)$ Boolean queries to the agents' preferences. This lower bound implies that Irving's algorithm is optimal for SR solvability (up to a logarithmic factor), and resolves an open question of Irving and Leather from 1989. The main result follows from a simple reduction from the communication complexity of the set disjointness function.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1342
LOCATION:
END:VEVENT
END:VCALENDAR