Math Talks: "A Stable Marriage Requires Communication," Will Rosenbaum '09 (Department of Mathematics, UCLA)
Thursday, February 26, 4:10 PM - 5:00 PM
Physics 123
This event is open to the public.
Lecture
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:
http://www.reed.edu/math/seminars/index.html.
Submitted by Kim Kadas.
Posted on Feb 13, 2015
- Tags
- Featured