Mon June 10.Our visitor Kanstantsin Pashkovich gave a talk on how to lower-bound sizes of extended formulations. Given a combinatorial optimization problem (matching, spanning tree, max-cut, traveling salesman problem, ...) one wants to find lower bounds on how many inequalities a Linear Program must have in order to model the problem.
The name "extended formulation" comes from the combinatorial optimization practice to start with a Linear Programming formulation, and then try to add a bunch of new variables together with (few) inequalities, so that the original inequalities become redundant.
Kostya explained the connection to Communication Complexity.
Discrete Lunch >