###### Cristopher Moore

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).

## Want to be notified about upcoming NetSI events? Sign up for our email list below!

Thank you! You have been added to our email list.

Oops! Something went wrong while submitting the form