My work addresses the algorithmic solution of problems which model situations that arise in practice, but for which there is strong theoretical evidence of intractability -- that is, on even modest-sized instances, the computational costs are excessively impractical. For instance, given a network of computers and links between them, we might wish to know how many computers need to fail before each survivor is connected to at most four others (or some small number). One approach would be to limit the type of networks considered to those exhibiting some property that makes the solution easier, and to choose properties which encompass networks used in practice. Another would be to ask whether or not the answer is bounded by some small number (say, ten), since in many instances we are only interested in an answer if it is small. My approach is to attempt to extend algorithmic techniques for these problems, while simultaneously looking for the theoretical evidence that might suggest that certain problems will remain intractable even under such restrictions. Here are links to a more technical summary of my work and a list of my publications (which may be missing the most recent ones).
I retain interests in such diverse areas as parallel computation, combinatorial optimization, and lower bounds on structured models in computation. In addition, I have always been interested in bringing theory to bear on the practice of computer science, an interest which dovetails naturally with the desire of many graduate students to do hybrid work. Thus I have been and am open to fruitful collaborations with colleagues in other fields. Recently, I have been learning more about the theory and practice of functional programming.
I am currently supervising two Ph.D students (both co-supervised).
Here are some recent papers, as of September 2007.
The paper "Solving #SAT using Vertex Covers" (PDF) will appear in Acta Informatica. The conference version appeared in the International Conference on Theory and Applications of Satisfiability (SAT), 2006.
The paper "Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems" (PDF) has been submitted to Algorithmica. The conference version appeared in the European Symposium on Algorithms (ESA), 2004.
Two twelve-author papers came out of a small by-invitation workshop on parameterized complexity and graph drawing. One is "On the Parameterized Complexity of Layered Graph Drawing" (PostScript), which appeared in the 9th European Symposium on Algorithms, September 2001. The journal version of this paper (considerably revised and expanded) has been accepted to Algorithmica and will be available in its final version soon. The other is "A Fixed-Parameter Approach to Two-Layer Planarization" (PostScript), which appeared in the 9th Conference on Graph Drawing, September 2001. The journal version of this paper was published in Algorithmica, volume 45, 2006.
The conference version of the paper "Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover", which appeared in WADS 01 (August 2001), is available in PostScript format. The journal version of this paper appeared in Discrete Applied Mathematics, issue 152, 2005.
The journal version of the paper "On graph powers for leaf-labeled trees", which appeared in the Journal of Algorithms, volume 42, 2002, is available in PostScript format.
The conference version of the paper "Embeddings of k-connected graphs of pathwidth k", which appeared in SWAT '00, is available in PostScript format. The journal version appeared in Discrete Applied Mathematics, volume 145, 2005.
My teaching assignments for 2009-10 are: CS 145 (Design, Abstraction, and Implementation) in fall 2009, CS 798 (Interpretation of Programming Languages) in fall 2009, and CS 442/642 (Principles of Programming Languages) in winter 2010. I expect to be on sabbatical in the academic year 2010-2011.
In winter 2006 and winter 2007, I developed a version of CS 245 that is more rigourous and more attuned to the rest of the CS curriculum than the one normally taught. In fall 2007, Brad Lushman took my slides and made a number of improvements. The next time I teach CS 245, I will use his version as a basis.
A summary of my teaching history is available, as are a few anecdotes. I also have an accumulating set of essays on teaching.
I serve on three university-level committees: as the Math Faculty representative on the University Tenure and Promotion Appeals Committee (in which capacity I act as an observer at meetings of the Science Promotion and Tenure Committee), as the Math Faculty representative-at-large on Senate Undergraduate Council (in which capacity I also sit on the Undergraduate Affairs Committee of the Mathematics Faculty), and the Instructional Technologies Advisory Committee, which advises the Associate Vice-President (Academic) on issues relating to teaching and learning.
In the School of Computer Science, I serve on the Undergraduate Recruiting and Space committees.
I was interim Director of First-Year Studies in Computer Science for the Faculty of Mathematics from January to July 2006. I could not serve a full term because of an impending sabbatical starting July 2007. Dan Brown returned from his sabbatical and took over the position.
From September 2003 to August 2005, I was on the University Appointments Review Committee (which reviews for the Provost all offers of faculty appointments made by Deans at the University).
From the time that Math Faculty Council moved to a representative format (see below) to August 2005, I was an elected representative from Computer Science on what was then called Representative Council. This Council met monthly to oversee academic policy and plans within the Faculty of mathematics.
From January 2002 to September 2004, I was a member of the Academic Board of the Independent Studies programme, which meets to approve the thesis proposals of students hoping to earn a Bachelor of Independent Studies.
From December 2000 to November 2003, I served on the Hagey Committee, which every year selects a distinguished lecturer to deliver the Hagey Lecture.
Until March 2004, I was one of the faculty representatives on the Teaching and Learning Technology Roundtable, an advisory panel reporting to the Associate Provosts and meeting monthly to assess, coordinate, and facilitate the implementations of learning technologies at UW. The Roundtable was replaced by a Teaching and Learning Council composed of winners of the Distinguished Teaching Award, and later resurrected as ITAC (see above).
From July 1998 to July 2002, I was the Associate Chair for Curricula of the Department of Computer Science, and in that role was chair of CS's Curriculum Committee. During that period I spearheaded the development of the new Bachelor of Computer Science degree and was chief negotiator for CS in the creation of the Bachelor of Software Engineering degree. I served as a member of that committee, now called the Undergraduate Academic Plans Committee, from July 1998 to July 2007.
In the period September 2000 to July 2002, I was a member of the CS Governance Committee whose report led to the formation of the School of Computer Science, and the Mathematics Governance Committee that redrafted the committee structure and bylaws of Mathematics Faculty Council, notably moving it from a committee of a whole to a representative council.
For something like three years, I sat on UW's Presidential Commission for Institutional Planning which commenced work in September 1994. The members of this commission were selected by the Provost, who chairs the committee; the mandate of the commission was to produce a White Paper on strategic and long-term planning for the entire University, and this was done, under the title "Building on Achievement", in fall 1997. This is also known as the "Fifth Decade" report.
I served on the Status of Women and Inclusivity Committee (SWIC) of the Faculty Association of UW from May 1995. From January to July 1997 I chaired this committee, which made me an ex-officio (nonvoting) member of the FAUW Board of Directors.
I was once the faculty advisor to the Gay and Lesbian Liberation Organization of Waterloo (GLLOW). Actually, the only reason I can claim this is that many years ago they needed someone to sign a form for CIBC that allowed GLLOW access to a bank account whose balance was approximately thirty dollars in the hole. That's all I ever did for them, but before doing it, I asked if I could put it on my CV. More recently, I performed a similar service for the Computer Science Club, but I have been taking a more active role for them.
For three years (July 1993-1996), I held an at-large seat (originally gained by acclamation) on the Academic Policy Committee of the Mathematics Faculty. In that time, the committee did not hold a single meeting. My replacement was also acclaimed to the post. Years later, without the committee ever having met, I managed to get it written out of the revised Math Faculty bylaws.