# A note on Probably Certifiably Correct algorithms

arXiv: https://arxiv.org/abs/1509.00824 · HTML: https://mlsanity.com/paper/1509.00824/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2015.

## Built on by (most cited first, 9 of 9)

- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Advances in Inference and Representation for Simultaneous Localization and Mapping](https://mlsanity.com/paper/2103.05041/) (2021)
- [Optimal Pose and Shape Estimation for Category-level 3D Object Perception](https://mlsanity.com/paper/2104.08383/) (2021)
- [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022)
- [Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Training](https://mlsanity.com/paper/2206.11215/) (2022)
- [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022)
- [Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras](https://mlsanity.com/paper/2101.08524/) (2021)
- [CLIPPER: Robust Data Association without an Initial Guess](https://mlsanity.com/paper/2402.07284/) (2024)
- [Sketch-and-solve approaches to k-means clustering by semidefinite programming](https://mlsanity.com/paper/2211.15744/) (2022)

## Abstract (arXiv)

Many optimization problems of interest are known to be intractable, and while there are often heuristics that are known to work on typical instances, it is usually not easy to determine a posteriori whether the optimal solution was found. In this short note, we discuss algorithms that not only solve the problem on typical instances, but also provide a posteriori certificates of optimality, probably certifiably correct (PCC) algorithms. As an illustrative example, we present a fast PCC algorithm for minimum bisection under the stochastic block model and briefly discuss other examples.