Maria Louisa Bonet

DIMACS - SYLA Postdoc


Interpolation theorems and Cutting Planes propositional systems.

DIMACS Center - Room 431
Busch Campus
Piscataway, New Jersey
September 27, 1995 at 1:00 PM

Abstract:

This will be a general overview on cutting planes propositional proof systems. Different ways to extract monotone circuits from cutting planes proofs will be presented. These give different lower bounds on the lengths of proofs that will be discussed.