Cristopher Moore
London E1W 1YW, UK
Portland, ME 04101
2nd floor
11th floor
Boston, MA 02115
2nd floor
London E1W 1LP, UK
Talk recording
What happens when an optimization problem has a good solution built into it, but which is partly obscured by randomness? Here we revisit a classic polynomial-time problem, the minimum perfect matching problem on bipartite graphs. If the edges have random weights in [0,1], Mézard and Parisi — and then Aldous, rigorously — showed that the minimum matching has expected weight zeta(2) = pi^2/6. We consider a “planted” version where a particular matching has weights drawn from an exponential distribution with mean mu/n. When mu < 1/4, the minimum matching is almost identical to the planted one. When mu > 1/4, the overlap between the two is given by a system of differential equations that result from a message-passing algorithm. This is joint work with Mehrdad Moharrami (Michigan) and Jiaming Xu (Duke).