University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Department Seminar by Cristopher MooreExport this event to calendar

Wednesday, October 21, 2020 — 11:00 AM EDT

Please Note: This seminar will be given online.

Probability Seminar Series

Cristopher Moore, Professor
Santa Fe Institute

Link to join seminar: Hosted on Webex.

The Planted Matching Problem


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

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2021 (12)
    1. May (1)
    2. April (5)
    3. March (4)
    4. February (2)
  2. 2020 (70)
    1. December (3)
    2. November (11)
    3. October (16)
    4. September (7)
    5. August (5)
    6. July (3)
    7. June (2)
    8. May (1)
    9. March (4)
    10. February (4)
    11. January (14)
  3. 2019 (65)
    1. December (3)
    2. November (8)
    3. October (8)
    4. September (4)
    5. August (2)
    6. July (2)
    7. June (2)
    8. May (6)
    9. April (7)
    10. March (6)
    11. February (4)
    12. January (13)
  4. 2018 (44)
  5. 2017 (55)
  6. 2016 (44)
  7. 2015 (38)
  8. 2014 (44)
  9. 2013 (46)
  10. 2012 (44)