Last day of Stephen Cook celebration

Stephen Cook and Michael Soltys at Hart House, UofT

Today is the last day of the conference at the Fields Institute dedicated to Stephen Cook, and 50 years of Complexity Theory. Stephen Cook was my PhD advisory starting in 1997, at the University of Toronto. I had two undergraduate degrees, one in Mathematics and one in Computer Science, and a masters in Mathematical Physics. I was looking for a topic for my PhD thesis, and I after working in algorithms for my masters, I approach Stephen Cook at the department of Computer Science, and he suggested to me that I read a book on Boolean Circuits by Ingo Wegener called The Complexity of Boolean Functions; I became immediately intrigued by the topic. I remember that I was fascinated by a result of Claude Shannon contained in Wegener’s book showing that there are “many more Boolean functions than Boolean circuits of small size”, and that therefore there have to be Boolean functions that required exponential size circuits. Once Stephen Cook accepted me as one of his students, he proposed that I read Samuel Buss‘ book Bounded Arithmetic, which became my introduction to the field of proof complexity. For my PhD thesis I worked on the problem of formalizing Linear Algebra in weak theories of bounded arithmetic, culminating with my 2001 thesis The Complexity of Derivations of Matrix Identities.

Alasdair Urquhart walking to the Fields Institute

It was a wonderful experience during the last few days to see so many colleagues and friends at the conference at the Fields Institute, celebrating the legacy of Stephen Cook. The department of Computer Science has long been a center of Theoretical Computer Science, Complexity and Proof Complexity. One of my mentors, and now friend, is Alasdair Urquhart, who spanned both the department of Philosophy and Computer Science, and whom I was lucky to have on my PhD committee, and who gave me a lot of guidance during my PhD years (for example, using lambda calculus as part of my formalization of a constructive theory of matrices for my PhD thesis).