Date and place: Nov. 5th, 13:30-14:30, ELC seminar room

speaker: Pavel Pudlák (Mathematical Institute of the Academy of 
Sciences of the Czech Republic)

title: Proof systems for Integer Linear Programing and monotone computations.

abstract: Many proof systems for Integer Linear Programing have been 
studied. However, there are only a few for which exponential lower bounds
 have been proven. One system for which no unconditional lower bounds are
 known is the Lovasz-Schrijver system (with DAG-like proofs). We will 
show a reduction of proving lower bounds for this system to proving lower 
bounds on a computational model "monotone linear programs". This is a new
 model for computing monotone Boolean functions based, as the name 
suggests, on linear programs. We mention some properties of the model; in
 particular, that it is strictly stronger than monotone Boolean circuits.
 Furthermore, we explain a connection to lower bounds on extended 
formulations in combinatorial optimization.


Part of these results is a joint work with Pavel Hrubes and
Mateus de Oliveira Oliveira.

* Please note that this seminar is a blackboard type informal one,
  more formal one will be held in Kyoto next week.
* Host: Osamu Watanabe (watanabe@is.titech.ac.jp)