Fall 2020

The Planted Matching Problem

Nov. 10, 2020 11:00 am12:00 pm

Add to Calendar


Cris Moore (Santa Fe Institute)


Zoom link will be sent out to program participants.

What happens when an optimization problem has a good solution built into it, but which is partly obscured by randomness? Here we revisit the classic assignment problem, i.e., the minimum perfect matching problem on bipartite graphs. If the edges have random weights in [0,1], Mézard and Parisi conjectured — and then Aldous proved — 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).