Seminars & Colloquia Calendar

We draw connections between descriptive complexity theory and combinatorial optimization to show that the ellipsoid method for solving linear programs can be implemented in a way that respects the abstractions and symmetry of the program being solved. That is to say, there is an algorithmic implementation of the method that does not distinguish, or make choices, between variables or constraints in the program unless they are distinguished by properties definable from the linear program.

In particular, we demonstrate that the solvability of linear programs can be expressed in fixed-point logic with counting (FPC) as long as the program is given by a separation oracle that is itself definable in FPC. We use this to show that the size of a maximum matching in a graph is definable in FPC. This refutes a conjecture first posed by Blass, Gurevich and Shelah (1999). On the way to defining a suitable separation oracle for the maximum matching program, we provide FPC formulas defining canonical maximum flows and minimum cuts in undirected weighted graphs.

This is joint work with Anuj Dawar.