BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//RLASKEY//CALENDEROUS//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VEVENT
DTSTAMP:20261004T103726Z
LAST-MODIFIED:20191205T153600Z
DTSTART:20191209T150000Z
DTEND:20191209T160000Z
UID:event2249@bu.edu
URL:http://physics.bu.edu/internal/events/show/2249
SUMMARY:The Planted Matching Problem
DESCRIPTION:Featuring Cris Moore\, Santa Fe Institute\n\nWhat happens when 
	an optimization problem has a good solution built into it\, but which is pa
	rtly obscured by randomness? Here we revisit a classic problem\, the minimu
	m perfect matching problem on bipartite graphs. If the edges have random we
	ights in [0\,1]\, Mézard and Parisi used the cavity method of spin glass t
	heory to predict that the minimum matching has expected weight zeta(2) = pi
	^2/6\, and Aldous then proved this using the framework of local weak conver
	gence. We consider a planted model where a particular matching has weights 
	drawn from an exponential distribution with mean mu. We show (rigorously) t
	hat there is a phase transition at mu=1/4 between perfect and partial recov
	ery of the planted matching: when mu  1/4\, the overlap between the two is 
	given by a system of differential equations that result from a message-pass
	ing algorithm. This is joint work with Mehrdad Moharrami (Michigan) and Jia
	ming Xu (Duke).
LOCATION:SCI 352\, 590 Commonwealth Avenue\, 02215
STATUS:CONFIRMED
CLASS:PUBLIC
END:VEVENT
END:VCALENDAR