Math Talks: "A Stable Marriage Requires Communication," Will Rosenbaum '09 (Department of Mathematics, UCLA)
Thursday, February 26, 4:10 PM - 5:00 PM
This event is open to the public.
Will Rosenbaum ’09, Department of Mathematics, UCLA
Mathematics Talk: A Stable Marriage Requires Communication
Thursday, February 26, 2015, 4:10 p.m., Physics 123
In this talk, we introduce the stable marriage problem, a classical problem in discrete math, economics, and computer science. Following the celebrated work of Gale and Shapley, we describe a simple algorithm which efficiently finds a stable marriage for any instance of the problem. After a brief foray into the world of communication complexity, we prove communication lower bounds for the stable marriage problem. As a consequence, we are able to show that Gale and Shapley's algorithm is, in a very strong sense, optimal. This talk presumes only high-school level mathematics, and should appeal to anyone with an interest in discrete math, economics, or computer science.
All are welcome. Free and open to the public. Refreshment will be provided.
For more information, visit:
Submitted by Kim Kadas.
Posted on Feb 13, 2015
Questions may be directed to Robin Tovey, communications manager. Announcements do not represent the views of Reed College.