17 citations · 30 across the 11 of their papers we have counts for
3 papers · 1 filter
Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances
Hunter Lang, Aravind Reddy, David Sontag +1
Several works have shown that perturbation stable instances of the MAP inference problem in Potts models can be solved exactly using a natural linear programming (LP) relaxation. H…
Graph cuts always find a global optimum for Potts models (with a catch)
Hunter Lang, David Sontag, Aravindan Vijayaraghavan
We prove that the -expansion algorithm for MAP inference always returns a globally optimal assignment for Markov Random Fields with Potts pairwise potentials, with a catch: the…
Block Stability for MAP Inference
Hunter Lang, David Sontag, Aravindan Vijayaraghavan
To understand the empirical success of approximate MAP inference, recent work (Lang et al., 2018) has shown that some popular approximation algorithms perform very well when the in…