Charlie Colbourn and Anna Lubiw made it possible for me to return to the University of Waterloo for my Ph.D. I approached Charlie (who was my M.Math. adviser) for possible funding in 1992-93 for my Ph.D. studies. Charlie had then over committed his funds (anyone who knows Charlie knows the amazing number of students he supports at any one time). But Charlie asked Anna to see if it would be possible for her to provide me with financial support instead. Anna’s agreement allowed me to return to Waterloo in April 1994. Anna also served as my first Ph.D. adviser. For this, I want to put on record here, my thankfulness to both Charlie and Anna.

I maintained an office at the Davis Center throughout my Ph.D. studies.

I wrote and passed the qualifying exams in October 1994.

As course requirements, I completed the four courses below (in chronological order):

• Parallel Computation (Instructor: Naomi Nishimura)
• Formal Languages and Number Theory (Instructor: Jeff Shallit)
• Semidefinite Programming (Instructor: Henry Wolkowicz)
• Readings in Combinatorics (Instructor: Charlie Colbourn)

I was a teaching assistant for Ming Li and Jonathan Buss. I was also a Unix consultant with the Math Faculty Computing Facility (MFCF).

In May 1994, Anna sponsored my trip to Montreal to attend STOC 94. I heard Michel Goemans’ talk on “0.878-Approximation Algorithms for MAX CUT and MAX 2SAT” and was immediately awed by the ingenuity and elegance of the semidefinite programming method for designing approximation algorithms. I decided that my thesis topic should be approximation algorithms. As Anna’s research interest lies primarily in computational geometry and graph theory, I studied the approximability of several such problems. These included the minimum weight triangulation problem, ε-nets, and the dense k-subgraph problem. My greatest success had been with the dense k-subgraph problem (which I submitted as a project for Wolkowicz’s course on semidefinite programming) but the results of Feige, Kortsarz and Peleg in “The Dense k-Subgraph Problem” has since superseded mine.

In 1995, I switched to Charlie Colbourn as my Ph.D. adviser. Alan Ling, who was then just completing his master’s thesis under Charlie Colbourn, must take both the blame and credit for my action. Around early 1995, Alan, knowing I was a former student of Charlie, showed up in my office almost everyday to discuss design theory problems. This has two effects. One, it distracted me from my research on approximation algorithms. Second, it rekindled my interest in design theory. So I asked Charlie again if it would be possible for him to support my Ph.D. studies and act as my adviser. This time, it was possible due to the graduation of some of his students. Charlie agreed and I made the switch. Alan of course continued to show up regularly in my office. Our interaction resulted in two papers: “On a Problem of Hartman and Heinrich Concerning Pairwise Balanced Designs with Holes” (with Charlie Colbourn and Rob Gallant) and “Uniform Group Divisible Designs with Block Sizes Three and n” (see publications page). We had a number of other results but we never find enough discipline to write them up.

Charlie got me started thinking about group testing problems when he passed me a draft of Balding and Torney’s paper “Optimal Pooling Designs with Error Correction”. I managed to obtain several new results here, both in the design of more efficient nonadaptive algorithms, and the characterization of optimal nonadaptive algorithms. When Alan and I were taking his “Readings in Combinatorics” course, Charlie introduced us to Hellerstein, Gibson, Karp, Katz, and Patterson’s paper “Coding Techniques for Handling Failures in Large Disk Arrays”. Together, we obtained some substantive improvements on that paper. I later also observed that both group testing problems and coding problems for disk arrays can be unified under the context of Turán-type problems. Based on these results, I began to write my thesis. When I was just about done, Boneh and Shaw presented their “Collusion-Secure Fingerprinting for Digital Data” paper at Crypto 95, which Stinson and Wei in “Combinatorial properties and constructions of traceability schemes and frameproof codes” immediately interpreted in the context of Turán-type problems. I noticed that some of the techniques for group testing problems carry over to fingerprinting for digital data, and I added a chapter to my thesis on new results for this problem.

In March 1996, I attended the Southeastern Conference on Combinatorics, Graph Theory and Computing held at Louisiana State University in Baton Rouge, where I gave a talk on my joint work with Charlie, “Constructions for Difference Triangle Sets”. At that conference, I saw Paul Erdős gave his plenary lecture and collapsed on stage to everyone’s shock. Erdős was brought to the hospital and recovered shortly after. But this would be the second and last Erdős lecture I attended (Erdős passed away on 20 September 1996 in Warsaw). Except for this unfortunately incident, I had a good time at the conference with Alan Ling and Zhike Jiang (the oyster dinner we had together was unforgettable). Food in Louisiana is simply fantastic. I especially like gumbo, crawfish etoufee, and blackened fish. I was also at Mardi Gras in New Orleans. It was an interesting experience to say the least.

In June 1996, I successfully defended my Ph.D. Thesis “Turán-Type Problems in Group Testing, Coding Theory and Cryptography” at the University of Waterloo. I was awarded an “A” by the thesis committee for my defence.

My thesis committee comprises:

I was conferred Ph.D. in Computer Science by the University of Waterloo at the Fall Convocation in 1996. I also received the “Outstanding Achievement in Graduate Studies” Award at the Convocation.

Those years of my Ph.D. studies were full of fun. Charlie, Alan, and myself met regularly in the “smoking room” on the 5th floor of MC Building

because Charlie needed his smoke. I had a lot of second-hand smoke for two years. Even the walls of that room had turned yellow from the smoke. But for the opportunity to discuss design theory with Charlie, it was all worth it. I also want to put on record here my profound gratefulness to Charlie Colbourn for his financial support, mentorship, and friendship throughout my university studies (from B.Math. to M.Math. to Ph.D.) and the years between and after. I shall remain forever indebted.