In the summer 2017, while I was teaching COMP 524 (Cybersecurity) at California State University Channel Islands, the students were introduced to a project based on an R&D from the SoCal High Technology Task Force (HTTF). The requirements and specifications asked for a device that could automate the search through vast amounts of data contained in portable devices (such as hard disks and thumb-drives), looking for pre-established patterns in file-names.
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.
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).
I’m happy to be participating at the 50 Years of Complexity Theory: A Celebration of the Work of Stephen Cook, whom I was fortunate to have as my PhD advisor at the University of Toronto. Tonight’s opening lecture by Christos Papadimitriou.