Colloquium Details
Average-case Solutions to Hard Problems
Speaker: Mark Braverman, University of Toronto
Location: Warren Weaver Hall 1302
Date: February 18, 2011, 11:30 a.m.
Host: Denis Zorin
Synopsis:
Many important computational problems are affected by various computational barriers that make them intractable in the worst case. In spite of this, it is often possible to get around these barriers and produce useful, if not optimal solutions for most instances of the problem. I will use several examples from my work to illustrate how considering an average or a typical case of the problem can be used to produce useful algorithms and mechanisms.
The first example deals with the problem of assigning medical graduates to residency programs in the presence of married couples. The problem of finding a stable matching between residency programs and doctors without couples is solved by the famous Gale-Shapley algorithm. In the presence of couples, such a matching may not exist, and it is NP-hard to determine whether it exists or not. Still, in a large random market we show how to find a good stable outcome with high probability.
The second example deals with aggregating noisy comparison signals, such as sport competition results, into a ranking most consistent with the observed signals. The worst-case version of the problem, known as the Minimum Feedback Arcset problem is NP-hard. We give an efficient algorithm for the average-case version of the problem.
Speaker Bio:
Mark Braverman is an assistant professor of mathematics and computer science at the University of Toronto. He received his PhD in 2008 under the supervision of Stephen Cook, and spent two years as a postdoctoral researcher with Microsoft Research New England in Cambridge, MA. He is the recipient of an NSERC Doctoral Prize and the Canadian Mathematical Society Doctoral Prize. Mark’s major interests are in the areas of computational complexity, algorithms, mechanism design, and applications of information technology in healthcare.
Notes:
In-person attendance only available to those with active NYU ID cards.