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.