Research students

September 11th, 2011

I welcome research students at all levels from undergraduate to PhD (I have also supervised a postdoctoral research fellow). The important things to know about me as a supervisor are:

  • A student project is a partnership (the more advanced the level, the more direction is left to the student). The amount of work that I put in will be proportional to the amount of work that the student does.
  • Provided the student works hard, I will do my absolute best to ensure that the student gains as much as possible from the experience.
  • I am best motivated by very good students who have a lot of initiative and ask a lot of good questions.
  • I respond much better to students who are well prepared for our regular meetings

I have a list of possible research topics suitable for students, which you should browse if you think you may be interested in me as a supervisor. I am always on the lookout for sources of funding for research students. Good NZ resident students have access to more sources of government funding, so my main effort is going into supporting non-resident students. Please see the department policies for COMPSCI 380 (undergraduate) or COMPSCI 780 (postgraduate), COMPSCI 789 (Honours) projects.

Possible research topics

I try to keep these up to date, but you should contact me for the latest ideas. I am always happy to be flexible if a good student really wants to work on a particular topic of the student’s own choosing.

Projects

Many topic ideas come down to implementing algorithms arising from my research, such as

  • computing asymptotic expansions for coefficients of generating functions. Will need to learn the basics of generating functions, but mostly this is about choosing data structures and learning the Maple or Python programming language.
  • converting a multivariate recurrence relation into a generating function, using the “kernel method”. Will need to learn the basics of generating functions, but mostly this is about choosing data structures and learning the Maple or Python programming language.

Others involve implementing a recently discovered algorithm for an important computing problem, and comparing performance against standard algorithms for the same problem using a mixture of theoretical and careful experimental analysis. Examples include

  • library sort of Bender et al
  • the greedy heuristic for Dodgson’s voting rule by Homan and Hemaspaandra
  • QuickRank by Greenwald and Wicks
  • Various interesting linear time string algorithms by Crochemore and others

Another category is performing computer-assisted explorations to give insight into phenomena about which we may be able to prove something (“experimental mathematics”). Examples include

  • properties of various voting rules such as susceptibility to manipulation and bribery. Will need to learn basics of voting theory, but mostly involves exhaustive search and clever programming to squeeze out as much speed as possible.
  • some recently discovered permutation statistics and determine their relation with known statistics. Basics of permutation statistics to be learned.
  • certain combinatorial games (even some very simple children’s games are not at all trivial to analyse)

A final category is designing and implementing a system that will assist with my teaching/research activities (these are more likely to be good for Software Engineering Year 4 projects). For example:

  • (VoteLib) creating a standard data format and web portal for (real and artificial) voting data to be used by voting theory researchers

Some past projects:

  • Mile Gu, COMPSCI 380 summer 2002/3. Wrote a Maple package to convert recurrence relation to generating function.
  • Erin Higgins, COMPSCI 380 summer 2002/3. Wrote Maple routines to help with computation of asymptotics of generating functions.
  • Erin Higgins, Faculty of Science summer scholarship, 2002/3.
  • Fangmin Chen, Faculty of Science summer scholarship 2005/6. Wrote Maple routines to help with computation of asymptotics of generating functions.
  • Egor Ianovski, COMPSCI 380 2010. Solved an open problem (safe manipulation of the Borda rule), leading to a publication in IJCAI, the main international AI conference.
  • Egor Ianovski, COMPSCI 789 2011.

Master’s theses

The MSc degree at this university contains no coursework and is to be completed within one year. Given this short timeframe, it is not expected that the student make a contribution to the research literature, although that is of course desirable. It is expected that the student show mastery of the current research literature in a specialized area. Typically I will list topics of current interest (to me at least, but usually I have heard of them somewhere else!) from the general area of algorithms. Possible topic ideas:

  • the automated analysis of holonomic sequences in computer algebra systems
  • ranking systems (such as Google PageRank) in the framework of social choice theory
  • correctness proof methods for greedy algorithms
  • cache-oblivious algorithms and their analysis
  • effect of chip architecture (branch prediction schemes) on algorithm performance
  • how to blend average-case analysis and competitive analysis for online algorithms
  • analysis of subtree-prune-regraft procedure for phylogenetic trees
  • smoothed analysis of algorithms (introduced by Spielman and Teng)

PhD theses

These are obviously more open-ended and more time can be devoted to them. Also the student’s interests are even more important, because you can’t do a good job over 3-4 years unless you are really interested in the subject. Possible topic ideas:

  • how to blend the methods of average-case analysis and approximation algorithms – there exist approximation algorithms whose worst-case factor over optimal is much worse than the average-case
  • current topics in computational social choice

Useful research links

Comments are closed.