Robust model fitting plays a vital role in computer vision, and research into
algorithms for robust fitting continues to be active. Despite the active
efforts, an important question remains: to what extent is robust fitting
computationally solvable? To answer this question, this talk presents several
computational hardness results for robust fitting. Unfortunately, the results
will show that robust fitting is not only intractable to solve, it is also
impossible to approximate. This talk then suggests a couple of ways to more
fruitfully expand the exisiting toolbox of robust fitting: specifically,
preprocessing techniques, and deterministic local search algorithms