Exponential lower bounds are proved for the length-of-resolution refutations of sets of
disjunctions constructed from expander graphs, using the method of Tseitin. Since these …

As introduced by Chvátal, cutting planes provide a canonical way of proving that every
integral solution of a given system of linear inequalities satisfies another specified inequality …

Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This
paper shows that there are Frege proofs of this propositional pigeonhole principle of …

An attractive way of looking at Gomory's cutting plane technique [13] was intro-duced by
Chvátal [5]. The point of view is that cutting planes provide a canonical way of proving that …

In Part I of the survey we highlighted the main stages in the development of methods of
automatic theorem proving, identified a number of directions that merit special attention, and …