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.