Campus Announcements

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

Announcements home page

Questions may be directed to Robin Tovey, communications manager. Announcements do not represent the views of Reed College.