## Complexity Theory and Model Theory Seminar Series

Organizers: B. Hart
and T. Pitassi

### Presentations

April 11, 2001

Alisdair Urquhart, Philosophy Dept, Univ. of Toronto

*The independence of the pigeon hole principle: a nonstandard model
theoretic proof*

March 28, 2001

Raf Cluckers, Leuven

*Infinite pigeonhole principles and Grothendieck rings of definable
sets*

Feb. 14 , 2001

Steve Cook, Toronto

*A model-theoretic proof of the Buss Witnessing Theorem*

Feb. 7, 2001

Dugald MacPherson, University of Leeds

*Asymptotics of definable sets in finite structures*

Dec. 4 , 2000

Alan Woods, Western Australia

*Colouring rules for finite trees, and probabilities of monadic second
order sentences*

Nov. 8, 2000

Deirdre Haskell, McMaster

*Quantifier Elimination from a model theorists point of view*

Oct. 25, 2000

Alisdair Urquhart, Toronto

*Riis’s Complexity Gap for Tree Resolution*

Oct. 11, 2000

Bradd Hart, McMaster

*The independence property and Vapnik-Chervonenkis dimension*