Technical report:

    Samuel R. Buss.
    "Lectures on Proof Theory."
    Technical Report number SOCS-96.1, School of Computer Science, McGill University 1996, 117 pages.

    Scribe notes from a series of lectures held in Bellairs Research Institute, Holetown, Barbados, March 1995.

    Scribes: K. Regan, J. Toran, A. Maciel, E. Allender, P. McKenzie, P. Clote, M. Bonet, R. Raz, C. Zamora, C. Lauteman, T. Pitassi.
    Editor: Denis Therien

    Download notes: postscript or PDF.

    Contents:

1. Proof Theory and Complexity (36 pages).
2. Interpolation Theorems for Propositional Logic (20 pages)
3. Natural Proofs and Split Versions of Bounded Arithmetic (18 pages).
4. Buss's Simplified ALOGTIME Algorithm for Boolean Sentence Evaluation (12 pages)
5. Bounded Arithmetic (16 pages)
6. Cutting Planes Proof Systems (12 pages)

Back to Sam Buss's publications page.