Optimality of belief propagation for random assignment problem

The assignment problem concerns finding the minimum-cost perfect matching in a complete weighted n x n bipartite graph. Any algorithm for this classical question clearly requires Ω(n²) time, and the best known one (Edmonds and Karp, 1972) finds solution in O(n³). For decades, it has remained unknown whether optimal computation time is closer to n³ or n². We provide answer to this question for random instance of assignment problem. Specifically, we establish that Belief Propagation finds solution in O(n²) time when edge-weights are i.i.d. with light tailed distribution.