The Planted Matching Problem

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=9LBKq5UU2D0


Duration: 58:33
574 views
6

Cris Moore (Santa Fe Institute)
Probability, Geometry, and Computation in High Dimensions
Seminar, Nov. 10, 2020

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



Other Videos By Simons Institute for the Theory of Computing


2020-11-24Reductionism in Reinforcement Learning
2020-11-11Reinforcement Learning
2020-11-11Sketching, Sampling and Sublinear Time Algorithms
2020-11-11Causal Inference
2020-11-11Computational Complexity of Statistical Estimation
2020-11-11Algorithms with Prediction
2020-11-11Networks and Graphical Models
2020-11-11Geometric Aspects of Sampling and Optimization
2020-11-10Economics and Learning
2020-11-10Overview of FODSI
2020-11-10The Planted Matching Problem
2020-11-10Is Your Distribution In Shape?
2020-11-04Work in Progress: a Structured Sampling Package
2020-11-04Thin Shell Estimates for Maximal Affine Surface Area
2020-11-04Capacity Bounds via Productization
2020-10-30What Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?
2020-10-30An Alternative Softmax Operator for Reinforcement Learning
2020-10-30On the Global Convergence and Approximation Benefits of Policy Gradient Methods
2020-10-30Corruption Robust Exploration in Episodic Reinforcement Learning
2020-10-30Representation Learning and Exploration in Reinforcement Learning
2020-10-29Multiplayer Bandit Learning - From Competition to Cooperation


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing