Events

Past Event

Stable Matchings

January 21, 2020
10:10 AM - 11:10 AM
America/New_York
Department of Computer Science, 500 W. 120th St., New York, New York 10027 Conference Room 453
Faculty Recruiting Colloquium Computer Science Department Robbie Weber, University of Washington ABSTRACT We will discuss the stable matching problem: Given two sets of agents (entities with preferences), our goal is to pair them off, while respecting the preferences of everyone involved. Algorithms for this problem have been used to match students to high schools, doctors to hospitals, and TAs to courses among many other applications. Stable matchings have proven so useful that the popularizers of the problem and the associated algorithms were awarded the 2012 Nobel Prize. We will discuss a beautifully-simple algorithm for solving the problem; if time permits we may very briefly discuss some questions about stable matchings that are the subject of active research. We will assume only a basic familiarity with programming and proofs (completion of COMS W3203 would suffice); much of the talk will be accessible even without that background. BIO Robbie Weber is a Ph.D. candidate advised by Shayan Oveis Gharan and Anna Karlin in the Theory Group at the Paul G. Allen School of Computer Science & Engineering at the University of Washington. His research is broadly in algorithm design for graph problems and combinatorial questions. He spends most of his time teaching a wide array of theory and theory-adjacent courses.

Contact Information

Adam Cannon