#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Professor Emeritus and Founding Chair (1924-2012)

Gerry Berman, Professor of Mathematics and founding Chair of the C&O department, died Sunday, September 16, 2012.

Born November 12, 1924 in Semens, Saskatchewan, his family moved to Toronto. After attending Harbord Collegiate Institute he studied at the University of Toronto, obtaining a PhD degree in 1950. His thesis topic was "Finite Projective Geometries," written under the supervision of H.S.M. Coxeter. While writing his thesis, he for a time shared an office with Tutte.

For the next nine years he taught at the Illinois Institute of Technology in Chicago.

Berman joined the faculty of the new University of Waterloo as Professor in 1959. He was, until Tutte came in 1962, the academic advisor for Ron Mullin's graduate studies. He and Ron each played a significant role in bringing Tutte to Waterloo.

In the initial planning for the Faculty of Mathematics in 1966, there were four projected departments. Berman went to Tutte, asking if he would be willing to form the nucleus of a fifth department: Tutte readily agreed. The first name chosen was the Department of Mathematical Science. Then Berman asked Tutte for a single term for graph theory, enumeration and design theory. Tutte replied: "The word is 'combinatorics'". Gerry added "and optimization," and thus it has been. He made C&O a comfortable home for Tutte, becoming a ready agent for Tutte's suggestions.

In its first year, 1967, the department's professors were Berman, Tutte, Nash-Williams, Mullin, Honsberger and Murty; Younger was a visiting professor, who stayed on. The Lecturers that year were Burns, Dodd, Dunkley, Faulkner, Haff, Miller, Morofke and Robertson.

Berman first got to know Charles Haff in 1960, when he was consulting for the Mathematics Department at Martin Marietta in Denver. In 1966, when Chuck asked Gerry for a letter of recommendation for graduate studies, Gerry turned it around, inviting Chuck to get his doctorate at Waterloo, with a lectureship. This was the beginning of a successful career for Professor Haff. It is only one of many examples in which Berman provided a home in C&O for different types of persons who went on to make significant contributions. I have in mind Davis, Fryer, Dunkley, Shank, Bondy, Edmonds, Jackson, Hammer, Read, Schellenberg, Best. He also made C&O a mecca for visitors.

Berman continued as chair until 1974; he retired as professor in 1989.

Gerry and his wife Molly were married for 66 years. They had four children: Ken, Ron, Sharon and David. Ken Berman was a student of C&O, and obtained a PhD under the supervision of Tutte; he is now a professor of Computer Science at the University of Cincinnati. Berman's sister Lorna lives in Waterloo; she taught French at Wilfrid Laurier University.

The Department of Combinatorics and Optimization, its name, its history, its initial character, are the legacy of Gerald Berman.

*- Dan Younger, Department of C&O*

Group(s):

In Memoriam

Professor Emeritus (1946-2021)

We are saddened to announce that our colleague and friend Michael Best, Professor of Combinatorics and Optimization at University of Waterloo, passed away on November 10 after a battle with cancer.

Mike earned his B.Math. and M.Math. degrees at the University of Waterloo in 1967 and 1968, followed by an M.Sc. and Ph.D. at UC Berkeley in 1970 and 1971. He was the second-ever recipient of a B.Math. degree at Waterloo. Mike joined the C&O faculty after his Ph.D., where he remained until his retirement in 2010.

Mike's research field was *optimization*. He was well known for his books on linear programming, quadratic programming, and portfolio optimization. He created and often taught the popular undergraduate course CO 372 on *portfolio optimization*. Mike supervised seven Ph.D. disserations at Waterloo, and thirty M.Math. students.

Group(s):

In Memoriam

Professor (1950-2021)

**Thomas F. Coleman**, a C&O Professor at the University of Waterloo, passed away after a battle with cancer on April 20, 2021 in Waterloo, Canada.

Tom was born on November 21, 1950 in Montreal, Canada, and completed high school in Toronto. Through the influence of a Math teacher in high school, Tom matriculated at the University of Waterloo, through the co-op program where students spend alternate semesters at school and in industry. After completing his Ph.D. under the supervision of Andy Conn at the C&O department at Waterloo in 1979, Tom spent two years as a postdoc at Argonne National Laboratory in Illinois. He held a faculty position in the Computer Science department of Cornell University from 1981-2005, and served as the Director of the Cornell Theory Center from 1998-2005. In 2005 he returned to Waterloo as the Dean of the Faculty of Mathematics and Professor of C&O, serving as Dean until 2010.

His early papers, several written jointly with Conn, addressed the convergence of nonlinear programming with exact penalty functions. At Argonne he began his investigation of combinatorial algorithms in optimization and scientific computing in papers co-authored with Jorge Moré on the use of graph colouring for efficient sparse Jacobian and Hessian estimation. Tom realized early that ideas from combinatorial optimization could significantly improve upon existing techniques for large-scale computation and continued to pursue this line of research throughout his career. Sparse matrix computation has long been a source of interesting problems linking combinatorial and scientific computing, and Tom’s first Ph.D. student, Alex Pothen, tackled the problem of finding a sparse null space basis for his dissertation. Through several students whom he guided in this research area, Tom could be considered as the father of the area now called **combinatorial scientific computing** (CSC). In 2018, researchers in CSC joined with other research sub-communities to form the SIAM Activity Group on Applied and Computational Discrete Algorithms (ACDA), and the first SIAM Conference on ACDA is being organized in July 2021.

In the 1990s, Tom developed the interior trust-region method jointly with Yuying Li, work that became part of the optimization toolbox in Matlab, and it became his most highly cited paper. A second computational issue that drew Tom’s attention during this period was automatic differentiation. Tom foresaw the significance of automatic differentiation for optimization and promoted the subject with publications, software tools, a book, and by organizing conferences.

At the same time, Tom developed an interest in optimization in the financial sector and wrote an influential sequence of papers on financial derivatives and portfolio optimization. He remained active in this area to the end of his career. In addition to his publications, he organized over a dozen conferences, workshops, and lecture series on the topic of optimization for finance. With his son Conrad, he also founded a consulting and software company, **Cayuga Research**, for more direct commercialization of his ideas.

Equal to contributions to scholarship were Tom’s leadership roles at Cornell and Waterloo. As the Director of the **Cornell Theory Center**, he sharpened its focus on research in scientific computing and financial computing and opened the Wall Street branch of the Theory Center in 1999, foreseeing the demand from Wall Street firms for the latest academic research.

Tom was appointed Dean of the Faculty of Mathematics at Waterloo, overseeing five academic departments and numerous programs and institutes, in 2005. Among his first actions as Dean was opening a Waterloo office on Wall Street. A delegation including Tom and other Waterloo leaders celebrated this event by ringing the stock exchange’s starting bell on November 23, 2005, an honour usually reserved for visiting heads of state and CEOs. Under Tom’s leadership, Waterloo’s Math Business programs grew, a graduate program in Computational Mathematics was created, the Faculty obtained funding for a new math building (the third on campus), and the Centre for Education in Mathematics and Computing (CEMC) obtained a large grant from the Gates Foundation. The CEMC has become the largest mathematics outreach organization in Canada and is known worldwide for its educational materials and grade- and high-school math contests.

After stepping down as Dean in 2010, Tom stayed active in research, teaching, and administration until his illness struck in 2020. He served a five-year term as Director of the Waterloo Research Institute in Insurance, Securities, and Quantitative Finance (**WatRISQ**) and held the Ophelia Lazaridis University Research Chair at Waterloo.

Tom was known for his careful preparation and thoughtful decision-making throughout his career that foresaw many major trends in mathematics and computing. He mentored 21 Ph.D. students, 18 postdoctoral fellows, and 18 Master’s students; these students hold leadership positions in academia, the U.S. DOE National Labs, and industry, especially in the financial sector. Tom’s students recall him as an exceptional mentor who was available to discuss research in a supportive manner, and who exuded an optimistic and practical outlook on research. He empowered them to think independently and encouraged them to take risks in research. Above all, by working hard, playing hard, and by developing close personal relationships with his students, he was a role model to them in living a full and balanced life. On hearing the news of his illness, many of them contacted Tom to let him know of the profound influence he had in their lives.

Tom was an active athlete throughout his life, enjoying cycling and canoeing with his family. Tom is survived by his wife, Yuying Li (a colleague in the computer science department at Waterloo), his children Conrad, Dan, and Lena, as well as his former wife, four siblings, nieces, and nephews.

*Alex Pothen, Steve Vavasis, Henry Wolkowicz*

Group(s):

In Memoriam

Professor Emeritus (1929-2016)

Ross Honsberger was born June 2, 1929 in Toronto. His father, Irwin, was a bookkeeper and his mother, Grace, before their marriage, a saleslady. After his retirement, Irwin had a home-based business, locating new and used books for customers, and also rebinding damaged books.

Ross attended Bloor Collegiate Institute, graduating in 1947. It was in high school that he met his future wife, Nancy Dawson. Another friend from that time was Frank Gehry, the architect. Reflecting on their lifelong friendship, Gehry said, "Ross and I in our high school days provoked each others' curiosities. He became the curious mathematical genius, and I the curious architect".

After high schoool, Ross entered the University of Toronto, graduating in 1950 with a BA degree. He decided to become a high school mathematics teacher. To this end, he took another year of mathematics and science courses at the University, and the following year obtained his teaching certification at the Ontario College of Education in Toronto.

Ross began his teaching career at Fisher Park Collegiate Institute in Ottawa. During his year there, he and Nancy were married. Ross then taught for ten years 1953-63 in the North York (Toronto) Board of Education, five years at Earl Haig Collegiate Institute, and five years as Department Head at Northview Heights Secondary School. During those years, Ross and Nancy's three children were born.

Among the students influenced by Ross are James Stewart and Michael Feldstein. Stewart, who became a mathematician and calculus textbook author, was asked in an interview what got him interested in mathematics. He responded by describing Ross, saying that he was "not your typical high school math teacher". Stewart was fascinated by Ross's "digressions"; for example, he proved in his grade 11 class that the rationals are countable and the reals are not. Feldstein, who went on to an academic career as a biostatistician, considers Ross his "first real mentor in mathematics and, more importantly, in teaching". He remembers especially the humour that Ross brought to his teaching, and his empathy for the students. Notably, while he took pains to obtain student feedback, Ross never embarrassed students by singling them out.

Ross was an active member of his profession, frequently giving talks to groups of mathematics teachers. Through such activities he came to know Ralph Stanton, who in 1957 took up a position as head of mathematics at what was to become the University of Waterloo. Stanton got Ross involved in the grading of the province-wide Grade 13 examination in Algebra, and in the production of the Ontario Secondary School Mathematics Bulletin. Ross eventually served as its managing editor for ten years.

The year 1963-64 was a pivotal one for Ross. He took a sabbatical from high school teaching and enrolled in a master's degree program at the University of Waterloo. Near the end of that year, Ralph Stanton offered Ross a position as a Lecturer in Mathematics. Ross asked if it was a permanent job, to which Ralph said "Yes", and they shook hands. Based on this, Ross resigned his high school job, repaid his sabbatical salary, and moved his family to Waterloo. During the next three years Ross carried a full teaching load while completing his master's degree. In 1967 he was promoted to Assistant Professor.

With his taste for elegance, his humour, and his enthusiasm, Ross was a popular lecturer. He made lecturing look easy. However, lurking behind this appearance, and evident in the notes he prepared, lay hours of meticulous preparation. Moreover, when he repeated a course offering, he never used his old lecture notes, but always created new ones.

In the sixties and seventies, there was a high demand for qualified high school mathematics teachers. Programs were needed for undergraduate mathematics majors at Waterloo interested in teaching as a career. In addition, many teachers already in service wanted to upgrade their qualifications. Ross played a leading role in addressing these needs. He developed several courses aimed at current and prospective teachers. Two notable ones were *History of Mathematics* and *Mathematical Discovery and Invention*. The latter became widely known as the *One Hundred Problems Course.* In addition to normal offerings, these courses were given in special six-week summer terms and by distance education. While their regular offerings were aimed at prospective teachers, they attracted many other students, partly due to Ross's reputation as an inspiring lecturer. Ross continued to give talks to groups of high school teachers and students. In 1971 when he was promoted to Associate Professor, Ross wrote "My main area of endeavour is prospective high school teachers and those already in service".

Ross's energy and ambition led him in another direction, too. From the beginning of his career, he had been searching out fascinating mathematical problems having elegant solutions, polishing them, and describing them in short essays. In the late sixties Ross submitted about forty of his essays to the New Mathematical Library series of the Mathematical Association of America (MAA). The editors selected nineteen of them for Ross's first book, Ingenuity in Mathematics, which appeared in 1970. Ross eventually produced thirteen books, all published through the MAA. When in 1974 a new MAA series, Dolciani Expositions, was created, Ross's book, Mathematical Gems, was chosen to be the first book in the series. Later, Ross chaired the committee of MAA responsible for the Dolciani series. The books sold well, and had considerable influence. Several were published in foreign language editions. Ross's writing enhanced his reputation, and, indeed, the reputation of mathematics at the University of Waterloo.

Ross's approach in his books can be summarized as follows (paraphasing the introduction to one of his books). Too often, the study of mathematics is undertaken with an air of such seriousness, that it is not fun at the time. However, it is amazing how many beautiful parts of mathematics one can appreciate with a high school background. Ross's goal in his writing was to describe such gems, not as an attempt to instruct, but as a reward for the reader's concentration. The success that Ross enjoyed was due to the combination of his superb taste in the choice of topics, and his talent and care in exposition. Ross also gave credit to Nancy for helping him to improve his writing.

When in 1967 the Department of Mathematics was replaced by a Faculty of Mathematics with five departments, Ross joined the Department of Combinatorics and Optimization. He became a highly valued member of that department. In 1971, when Ross was promoted to Associate Professor, a department colleague wrote in a supporting letter that Ross was "a research mathematician in the best sense of the word, i.e., a contributor to fundamental and original thinking about the nature of the subject as a whole".

Ross was a wonderful positive influence on those around him. He enthusiastically shared his latest elegant solution with everyone. Former colleagues recall Ross asking for a few minutes of their time, leading to much longer discussions. "Everyone" also included friends of his children that happened to come to the house. Accessibility to such friends was aided by the fact that, as his daughter Sandy recalls, "his office was our living room'.

As time passed, Ross stepped back from teaching to concentrate on his writing. He took a reduced load appointment in 1990, and early retirement in 1991. Ross did not teach in retirement, but his occasional special lectures drew large and enthusiastic audiences. Meanwhile, he devoted a lot of energy to his writing. Six of his books appeared after his retirement, the last in 2004.

Throughout his life Ross had wide interests, including reading, music, gardening, handball, darts, billiards, and poker. He always had a dog. And of course, there was his family. He cared for Nancy through her long battle with Parkinson's disease. She died in 2010. Ross remained in their home of more than fifty years until May 2015. After he was diagnosed with a cancer of the blood, he moved into assisted living. Ross continued to enjoy movies, music, and televised sports. There were frequent visits from friends and family, and from his dog, Barney, for whom a new home had been found.

Ross died April 3, 2016. In addition to his daughter Sandy, he is survived by three grandchildren and seven great grandchildren. He will be long remembered by his family, his friends, his colleagues, his students, and his many readers.

Group(s):

In Memoriam

Distinguished Professor Emeritus (1917-2002)

*The following biographical sketch was written for the October 2002 issue of CMS Notes: W.T. Tutte (1917-2002). View the full William T. Tutte page to see additional information about Tutte and the impact he had on the world of mathematics. *

**Biography of Professor Tutte - (1917 - 2002) **

William T. Tutte, Distinguished Professor Emeritus at the University of Waterloo, died May 2, 2002. The cause was congestive heart failure, complicated by lymphoma of the spleen, both diagnosed within six weeks of his death.

It was just a year previous, October 2001, that he was inducted as an Officer in the Order of Canada, in a ceremony held at Rideau Hall in Ottawa. The citation began "He is internationally renowned for his seminal work in the area of graph theory. As a young mathematician and codebreaker, he deciphered a series of German military encryption codes known as Fish". These two sentences speak to his place in history. His wartime codebreaking work, much emphasized in newspaper obituaries, was a secret by order of British security until 1993 and, indeed, is only described with detail in recent articles.

**Beginnings**

Bill Tutte was born May 14, 1917 at Fitzroy House in Newmarket, England. His father was the House gardener, his mother the caretaker. How he rose from this background to graduate from Trinity College, Cambridge, is as remarkable a chapter of his life as those that followed.

Fitzroy House is now, and was perhaps then, a horse racing stable. In Bill's first years, the family moved about with the vagaries of domestic employment until, when he was about three, they came to live in a house called Moorend, located high on the Yorkshire moor, in Aislaby, overlooking the Esk river, about three miles from Whitby and the east coast of England. His parents were the caretakers at Moorend. This is the place of first remembrances, where he first went to school. Then, only a few months after his beginning school, the family moved once again, back to the Newmarket area, to a little village Cheveley, three miles east of Newmarket centre. It so happens that the city of Cambridge lies fifteen miles to the west of Newmarket.

The family lived in a flint cottage, one half of a duplex, reached by a footpath adjacent to the 600 year old Anglican Church that dominates Cheveley. His father soon obtained the position of gardener at the Rutland Arms Hotel in Newmarket. This finally gave stability to family life: they lived in that cottage until his father's death in 1944.

Bill went to the village school, run by the Anglicans, from age six until eleven. He has spoken of the school as enlightened in its religious education and the possessor of a fine children's encyclopedia, which he frequently consulted. Aided by its contents, Bill developed a keen interest in astronomy.

He was a successful student: at age ten he took the scholarship examinations for secondary school. The schools in England were organized on a county basis and, through an ancient oddity of district boundaries, Cheveley lies in Cambridgeshire, even though Newmarket, in Suffolk, lies between Cheveley and the city of Cambridge. So when Tutte won a scholarship, it was to the distant school in Cambridge. Too distant, his parents judged, and he was kept at home. A year later he again took the examinations, with the same success. This time, at eleven, his parents took the headmaster's advice to enroll him at the Cambridge and County High School for Boys. It was to be for Bill a long daily commute, taking his bike into Newmarket and, if the weather was fair, on the further fifteen miles into Cambridge. Or, if it was foul, then take the train from Newmarket, with another mile's walk from the station at the far end.

In this school he further excelled in studies. A testament to this is a little shelf of books left in his office, each imprinted in gold on the cover with the school motto "Virtute et Fide" and with a plate inside inscribed by the headmaster. "Prize for Mathematics, Form VI", reads the inscription of "Shakespeare's Complete Works"; for "The Plays of John Galsworthy", it is "Prize for Chemistry, Form VI."

In 1935, he entered Trinity College, Cambridge. For his studies there he was, in his words, "adequately supported financially by a State Scholarship, a College Scholarship, and a grant from the County." As an undergraduate, Bill majored in chemistry. Indeed, he achieved First Class Honours therein, and went on to graduate study in that field. His first two publications describe experimental work in chemistry. But the evidence is clear that his primary interest, dating at least from his high school days, was in mathematics, though not perhaps in the fields most in vogue. From his first days at Cambridge, he participated regularly in the meetings of the Trinity Mathematical Society. There he met Cedric Smith, and then Leonard Brooks and Arthur Stone, like-minded undergraduates with whom he conducted researches in mathematics. They were mathematics majors; Bill formed a bond with these three that would remain close throughout their lives.

Not the first that they studied, but the one most remembered by history, was the problem of determining whether or not a square can be partitioned into smaller squares, all unequal in size. It arises from puzzle #40, Lady Isabel's Casket, in H.E. Dewdney's book "The Canterbury Puzzles".

It is, of course, not the puzzle but what they made of it that is remarkable. To begin they translated the problem to the language of electrical networks. In the 1940 paper that later described their work are formulas for electrical network functions, not just those found earlier by Kirchoff, but new ones for transfer functions. This paper became a standard reference for electrical network practitioners. The question of squaring the square, in electrical terms, became a study of rotational symmetry of a part of the network, and how reflection of the symmetric part can alter its currents without affecting potentials on its boundary. The level at which they conceived the problem is remarkably deep. Their method did succeed in finding partitions of squares into smaller unequal squares.

This was not the only memorable study that Tutte undertook in his initial period at Trinity, but the others were published later. For Tutte's academic career was put on hold by World War II.

In January 1941, upon invitation of his Tutor, Tutte went to Bletchley Park, the now legendary organization of code-breakers of Britain. It was later that year, in October, that Tutte encountered TUNNY, the first of a set of machine-ciphers named Fish. Now Fish is not Enigma. The Bletchley code-breakers, among whom Alan Turing was prominent, had had success in deciphering Enigma codes. But that success was with the naval and air force versions; the army version of Enigma proved to be resistant to analysis. That Bletchley could not read Army Enigma gave them incentive to attack Fish, which was used only by the Army. Moreover, Fish was used for high level communications between Berlin and the field commanders.

Tutte's great contribution was to uncover, from samples of the messages alone, the structure of the machines which generated these codes. This came about as follows. In August 1941, a German operator sent a Fish-enciphered teleprinter message of some 4000 letters from Athens to Berlin. For some reason, the message was not received properly and so it was resent. Against all guidelines, it was sent with the same setting. It was identical in content, but it differed slightly, in word spacing and punctuation. John Tiltman of Bletchley was able to use this blunder to find both the message and the obscuring string that was added to make up the enciphered message. But that seemed to be all that could be found, when Tutte was presented with the case in October.

Tutte began by observing the machine generated obscuring string carefully. Splitting it up into various lengths, he noticed signs of periodicity. For the first of the five teleprinter tape positions, the regularity he supposed arose from a wheel of 41 sprockets. And then at the last position, one of 23 sprockets. Over the next months, Tutte and colleagues worked out the complete internal structure, that it had twelve wheels, two for each of the five teleprinter positions, and two with an executive function. They determined the number of sprockets on each wheel, and how the advancement of the wheels was interrelated. They had completely recreated the machine without ever having seen one. Tony Sale, who first described this work in a 1997 article in New Scientist, characterized it as the "greatest intellectual feat of the whole war."

Knowing the structure of the enciphering machine is a necessity for code-breaking, but it is only the first step. Tutte then put himself to creating an algorithm to find from the enciphered messages the initial settings of the machine wheels. The algorithm that he created, the "Statistical Method", looked for certain types of resonances, but it had to consider far too many possibilities to be carried out by hand. So it was that, in 1943, the electronic computer COLOSSUS was designed and built by the British Post Office. It was to run the algorithms that Tutte; and his collaborators Max Newman and Ralph Tester; developed, that COLOSSUS was created. This man-machine combination was used to break Fish codes on a regular basis throughout the remainder of the War.

Acknowledgement from U.K. Prime Minister, David Cameron (PDF)

In late 1945, Tutte resumed his studies at Cambridge, now as a graduate student in mathematics. He published some work begun earlier, one a now famous paper that characterizes which graphs have a perfect matching, and another that constructs a non-Hamiltonian graph. He went on to create a ground-breaking PhD thesis, "An algebraic theory of graphs", in which he forges the subject now known as matroid theory.

Upon completing his degree, Tutte was invited by H.S.M. Coxeter to come to Canada, to join the Faculty of the University of Toronto. In his fourteen years at Toronto, beginning in 1948, he rose to preeminence in the field of combinatorics. One form of recognition in that period was his election as Fellow of the Royal Society of Canada.

It is difficult to describe in a summary way the many branches of research that Tutte pursued. Fortunately, Tutte has himself given such a summary, in his comments in the "Selected Papers of W.T. Tutte", published in 1979, and "Graph Theory as I have known it", in 1998. It is notable the degree to which these researches have their point of origin in squaring the square and matroids.

In 1962, Tutte joined the Faculty of the University of Waterloo. This was just five years after its creation. Tutte made a major contribution to establishing the identity and reputation of the University. His presence was a magnet for combinatorialists from all over the world. It was not only recognized stars of the field that came to Waterloo, but those of future prominence. Tutte was an important ingredient in the recipe that produced the Faculty of Mathematics in 1967, becoming one of the first members of the Department of Combinatorics and Optimization. He retired in 1985, but continued to be a significant member of the Faculty as Professor Emeritus. Until his retirement, he was Editor in Chief of the Journal of Combinatorial Theory.

Bill Tutte enjoyed hiking, and soon after his arrival in Canada became a member of the Canadian Youth Hostels Association. It was through the Hostel movement that he met Dorothea Mitchell, from Oakville: they were married in October 1949. Dorothea was lively and chatty, Bill more reserved in manner: they formed a lovely couple. When they moved to Waterloo, they lived out in the little village of West Montrose, just adjacent to the wooden covered bridge that is the signature of the region. Here the Tuttes managed an extensive garden, of mostly wild flora, on the banks of the Grand River. The neighbourhood is a pleasant place for hikes. Dorothea was an avid and skilled potter, well-known for her pivotal role in the founding of the Waterloo Potters workshop. For the Waterloo Combinatorics Conference of 1968, she made a personalized mug for each of the invited speakers, some thirty five in all. Dorothea died of cancer in 1994; they had no children.

Paul Seymour of Princeton University writes:

Professor Tutte has been for many years the dominant figure in graph theory, and his contributions to the subject outweigh those of any other individual (in every sense except perhaps quantity). There are numerous instances when Tutte has found a beautiful result in a hitherto unexplored branch of graph theory, and in several cases this has been a ´breakthrough´, leading to the development of a major new subject.

Lászlo Lovász of Microsoft writes:

Few theorems in mathematics are honored by the general public by naming them after the mathematician who proved them. In Tutte's case, however, there are several such results: for somebody working in matching theory, Tutte's theorem is his characterization of graphs having a perfect matching - for a matroid theorist, it means his characterization of regular matroids - for somebody studying Hamiltonian cycles it means his result that 4-connected planar graphs have a Hamilton cycle. And there is also the Tutte polynomial of a graph (and a matroid), which is again a household word for many combinatorialists.

Tutte was a master of phrasing: here are some examples. To begin, there is the phrase "squaring the square". Next, the term "wheel" is an apt description of the structure that lies at the heart of his analysis of 3-connected graphs; its nongraphical analog in matroid theory is "whirl". The title of a seminar describing a fatal flaw he had found in a famous mathematician's paper on 3-colouring was "Et tu, Tut-té!" The title of his famous paper on the Reconstruction Conjecture for graphs is "All the king's horses". In his penetrating analysis and reformulation of the Birkhoff-Lewis equations, he declares some of those equations to be "of mysterious provenance." Finally, one of his last public lectures was "Sixty years in the nets."

Tutte was awarded the Tory Medal by the Royal Society of Canada in 1975. He won the Killam Prize in 1982. Last year he was awarded the CRC-Fields Institute Prize; receiving this became the occasion for two of his last public lectures, the one referred to above in Toronto, the other in Montreal.

In 1987 Tutte was named a Fellow of the Royal Society of London.

*Dan Younger
August 2002*

Group(s):

In Memoriam

Distinguished Professor Emeritus (1947-2014)

Scott Alexander Vanstone passed away on March 2, 2014, at his home in Campbellville, Canada.

Scott was born in 1947. He received his PhD in mathematics in 1974, working under the supervision of Professor Ron Mullin in the Department of Combinatorics and Optimization (C&O) at the University of Waterloo. He was then a professor of mathematics at St. Jerome's University and Waterloo's C&O department, until his retirement in 2009. He was appointed distinguished professor emeritus of mathematics at the University of Waterloo in 2009.

Scott's early work was in combinatorial design theory. In the 1980's he started working in cryptography. One of his first contributions, with Blake, Fuji-Hara and Mullin, was an improved algorithm for computing discrete logarithms in characteristic-two finite fields. This work inspired Coppersmith to devise his famous L[1/3] algorithm in 1984. He also designed, with Agnew and Mullin, hardware architectures for implementing arithmetic in characteristic-two fields.

Scott became enthralled with elliptic curve cryptography (ECC) after hearing Victor Miller's talk at Crypto '85. In the subsequent years, he devoted much of his research to the security analysis and efficient implementation of ECC. Among his contributions was the Weil pairing attack (with Menezes and Okamoto) to efficiently transport some instances of the elliptic curve discrete logarithm problem to instances of the ordinary discrete logarithm problem in extensions of the underlying finite field. With Gallant and Lambert, he showed how efficiently-computable endomorphisms could be used to accelerate Pollard's rho attack on the elliptic curve discrete logarithm problem.

On the efficiency front, Scott developed algorithms and protocols that are especially well-suited for implementing ECC in environments where processor speed, bandwidth, or power consumption is severely constrained. With Gallant and Lambert, he developed an innovative technique for point multiplication on elliptic curves that have efficiently-computable endomorphisms. With Menezes and Qu he developed a key agreement protocol which was later standardized by IEEE, ANSI, NIST, ISO, and IETF. The *PV signature scheme*, jointly developed with Leon Pintsov, is an efficient short-signature scheme with message recovery that has been standardized by ANSI and used by Pitney Bowes in their design of digital postal marks. Scott also co-designed a comprehensive and efficient implicit certification scheme which enables derivation and verification of a purported public key of the certificate holder from the certificate, thereby obviating the need to include this information explicitly into the certificate itself and saving bandwidth.

Scott played an instrumental role in commercializing ECC. With Gord Agnew and Ron Mullin, he co-founded Certicom Corp. in 1985. He introduced ECC to several standards organizations including IEEE and ANSI, and played an active role in the development of the first ECC standards - ANSI X9.62 and IEEE P1363-2000. In the early 1990's he started evangelizing the benefits of ECC to numerous commercial entities, resulting in the adoption of ECC technology by companies such as Motorola, Pitney Bowes, and Research in Motion. Scott worked tirelessly for Certicom over the years, and served in numerous capacities including Chief Cryptographer and EVP for Strategic Technologies. He was also a member of Certicom's Board of Directors from its inception in 1985 until 2009 when Certicom was acquired by Research in Motion.

Over the years, Scott served the crypto community in several capacities. He co-founded the Data Encryption Group at the University of Waterloo, which evolved into the Centre for Applied Cryptographic Research. At Waterloo, he supervised seven PhD students and ten postdoctoral fellows in the area of cryptography. He was co-author of the popular reference books *Handbook of Applied Cryptography* (with Menezes and van Oorschot) and *Guide to Elliptic Curve Cryptography* (with Hankerson and Menezes), and an Editor-in-Chief of the journal *Designs, Codes and Cryptography* from 1990 to 1999. He co-founded the annual workshop on Elliptic Curve Cryptography in 1997. He was program chair of Crypto '90, and served on the IACR's Board of Directors from 1990 to 1996.

Scott held the NSERC/Pitney Bowes Industrial Research Chair in Cryptography at the University of Waterloo from 1998 to 2008. He was elected a Fellow of the Royal Society of Canada, Academy of Sciences in 1998. He received the Ontario Premier's Catalyst Award for Lifetime Achievement in Innovation in 2009. In 2011, he was elected a fellow of the International Association for Cryptographic Research (IACR).

Scott was an extremely generous, patient, tolerant and kind person. He was always positive and encouraging, and was an inspiration to his students, and to countless researchers and practitioners working in cryptography. He lived life to the fullest and, with his beloved wife Sherry Shannon-Vanstone, hosted many memorable parties at their house in Campbellville. He was an extraordinary scholar, teacher and mentor, and, above all, a dear friend. We all will miss him very much.

Group(s):

In Memoriam

- Administration (8)
- Faculty (36)
- Cross appointed | Adjunct (17)
- Postdoctorals | Visitors (16)
- Graduate students (70)
- In Memoriam (6)

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.