The goal of these seminars is to capitalize on the new additions to the logic scene in the greater Toronto area and to explore points of commonality between these two areas; talks are meant to be expository and informal. Meetings take place on select Mondays in the Fields Institute Boardroom. Look for announcements in the weekly seminar listings.

Organizers: Bradd Hart, McMaster University, Toniann Pitassi, University of Toronto

Schedule

November 12, 2002 Neil Thapen, University of Toronto.
Models of bounded arithmetic
Definition of theories, model-theoretic proof of witnessing theorem;
The weak pigeonhole principle; if it isn't provable in ID0, then ID0 isn't finitely axiomatizable;
WPHP for polynomial time functions; witnessing in probabilistic polynomial time; some consequences;
Characterization of WPHP as saying that large initial segments of a model are more complicated than small ones; co-ordinatization theorem; some speculation.

November 21, 2002 Neil Thapen, University of Toronto.
Models of bounded arithmetic II

December 5, 2002 Neil Thapen, University of Toronto.
Models of bounded arithmetic III

January 16, 2003 Neil Thapen, University of Toronto.
Models of bounded arithmetic IV

February 3, 2003 Neil Thapen, University of Toronto.
Models of bounded arithmetic V

February 10, 2003 Bradd Hart, McMaster University
Triangle-free graphs and the finite model property