Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Solving Linear Programs without Breaking Abstractions

Matt Anderson: Union College

Location:  CoRE 301
Date & time: Wednesday, 22 March 2017 at 11:00AM - 11:11AM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.