Monotone Boolean Functions, Feasibility/Infeasibility, LP-type problems and MaxCon

Understand

This paper outlines connections between Monotone Boolean Functions, LP-Type problems and the Maximum Consensus Problem.

• The latter refers to a particular type of robust fitting characterisation, popular in Computer Vision (MaxCon).
• Indeed, this is our main motivation but we believe the results of the study of these connections are more widely applicable to LP-type problems (at least 'thresholded versions', as we describe), and perhaps even more widely.
• We illustrate, with examples from Computer Vision, how the resulting perspectives suggest new algorithms.