Feasible Interpolation in Proof Systems based on Integer Linear Programming

Author: Pavel Pudlak

Paper Information

Title:	Feasible Interpolation in Proof Systems based on Integer Linear Programming
Authors:	Pavel Pudlak
Proceedings:	iPRA 2014 Proceedings
Editors:	Laura Kovacs and Georg Weissenbacher
Keywords:
Abstract:	Feasible interpolation has been proved for several proof systems based on integer linear programming. To prove such a theorem one has to design a polynomial time algorithm. The methods which are used to design these algorithms range from a very simple algorithm, used in the cutting plane proof system, to semidefinite programming, used in a version of Lovasz-Schrijver proof system. This reflects the increasing strength of the proof systems.
Pages:	1
Talk:	Jul 17 14:30
Paper: