Marshall Drew-Brook
Home university:
University of Waterloo
Supervisor:
Bertrand Guenin
Research results:
My work this past summer with Professor Guenin centred on a conjecture characterizing graphs which lack three disjoint odd-circuit covers. Specifically, I developed a program to assist in checking candidates for a key condition: namely, that every edge must lie in some (to be determined) local structure. Initial runs of the program generated an absolutely huge number of graphs to check, so I spent much time designing and implementing improved algorithms which, along with a new piece of blazing hardware, should cut processing time drastically.
Comments:
The Undergraduate Research Assistant (URA) program is fantastic. I thoroughly enjoyed the exposure to new ideas through meetings with my supervisor, Professor Guenin, discussions with fellow URAs, and weekly seminars. Anybody with a strong interest in mathematics should certainly apply to the program
Kenny Fong
Home university:
UWaterloo
Supervisor:
Alfred Menezes
Research results:
Completed implementation and analysis of the point halving method of Knudsen and Schroeppel for elliptic curve point multiplicaiton. A paper has been submitted to the IEEE Transactions on Computers.
Comments:
My work this year is a continuation of my work last year. However, it is interesting to note that I have learned very different things this year from last year's. The most valuable things that I learned last year are strategies in optimizing assembly codes. This year I've learned strategies in optimizing codes written in high-level programming languages, use of new hardware technologies (e.g. MMX/SIMD architecture) for optimization, and application of elegant math techniques to optimize point halving in special cases. Moreover, I really enjoyed working with Professor Darrel Hankerson and Professor Alfred Menezes, and the opportunity to give a talk. URA experiences are definitely helpful in future academic careers, but I would like to point out that URA experiences are also extremely helpful to you if you want to work in industrial research positions or in technology-based consulting firms.
Update 2008:
Senior Lecturer in the Department of Computer Science at Southern Illinois University Carbondale
Tony Chi Thong Huynh
Home university:
Simon Fraser
Supervisor:
Jim Geelen
Project title:
Generating Internally four - Connected Graphs
Comments:
I thoroughly enjoyed my summer at Waterloo, as I was very fortunate to have a consummate supervisor. We attempted to prove a theorem pertaining to Internally four-Connected Graphs that is an analogue of Seymour's Splitter Theorem for three-Connected Graphs. Such a theorem has been used for instance to limit the number of counterexamples to Negami's Planar Cover Conjecture. A pervasive method of proof was to exploit submodularity. We were able to prove a partial result that hopefully will lead to a complete proof. I also investigated some conjectures related to Hadwiger's Conjecture and attended a Conference on Matroid Structure Theory in Ohio. I certainly recommend the Combinatorics and Optimization URA program at Waterloo.
Luis Serrano
Home university:
UWaterloo
Supervisor:
Ian Goulden
Project title:
An extension of the reflection principle for counting lattice paths.
Research results:
I.P. Goulden and L.M. Serrano, A Rotation Bijection for Lattice Paths above a Line of Integer Slope, (a six page research paper, submitted for publication to J. Combinatorial Theory (A)). We were able to give a bijective geometrical proof of a result that counted the lattice paths from (0,0) to (m,n) without going below the diagonal of slope k.
Comments:
I was very glad to be given this opportunity. By working on a research problem, I learned a lot of theory and tools, and had a lot of fun in the process. My supervisor was great, and gave me the right hints and advice. In the seminars I had the opportunity to share our work with that of other students, and to get up to date with other problems in the field. In summary, it was an amazing experience which I recommend to anyone interested in research.
Update 2008:
PhD Student Department of Mathematics · University of Michigan
Matt Tucker
Home university:
UWaterloo
Supervisor:
E. Teske
Project title:
Factoring with Approximate Common Divisors
Research results:
Matt Tucker worked on a problem that is crucial for an efficient application of the so-called Extended Weil Descent Attack on the elliptic curve discrete logarithm problem. This attack, an extension of the Weil descent attack, exploits a correspondence between a certain class of elliptic curves (namely, the elements in a given isogeny class) and the ideal class group of a certain imaginary quadratic number field. To run the attack, a pseudo-random walk generated by ideal classes of small norms is used. In order that each step of the walk can be done fast, these norms must be chosen as small as possible. But in order to well simulate a random walk a minimum amount of ideal must be used as generators of the walk which unavoidably increases the norms involved. Matt used theoretical results on random walks combined with extensive computer experiments covering large ranges of discriminants and determined optimal choices for random walk parameters. These results are most valuable for future research on the impact of the extended Weil descent attack.
Martha Yip
Home university:
UWaterloo
Supervisor:
B. Richmond
Project title:
Random Primes and Components of Random Permutations
Research Results:
I worked with Professor Richmond and Professor Panario (from Carleton) on developing asymptotic formulas regarding the expected value of the logarithm of the rth smallest prime factor of N. As an application of our results, we analyzed a simple primality test and found the expected cost of the algorithm. The research resulted in a submitted paper.
Update 2008:
Graduate student, University of Wisconsin
Danny Sheng Zhang
Home university:
UWaterloo
Supervisor:
Dan Younger
Project title:
The dichromatic join matrix and its inverse
Research results:
I explored many ways to approach a generalized form of the inverse of dichromatic join matrix.
Comments:
Absolutely a valuable experience in my life. I learned a lot in graph theory and the relation between graph theory and its corresponding matrix forms. I appreaciated my supervisor's comments and directions, which helped me go through my hard time during research. Also, the URA seminars were an amazing part of the job. I enjoyed the time when giving a talk, as well as listening to other URA's "fun" talks.
Future plans:
Moving on to graduate studies
Jason Wong
Home university:
UWaterloo
Supervisor:
Alfred Menezes
Research results:
Bernstein's method of integer multiplication using floating point arithmetic was carefully implemented. Our implementation results have been included in a technical report on implementation of elliptic curve cryptosystems.