Grant: Discovery Grants Program - Individual

I investigate classic computer science topics (algorithms, data structures, networks) with a particular focus on topics that have a geometric or graph-theoretic component. My research program, which includes both theoretical and practical research, proceeds in three fundamental directions: (1) Worst-case analysis using the classic tools of asymptotic analysis and combinatorics. Recent examples include studying the worst-case running-time of a nearest neighbour search algorithm, the highest resolution required for a particular kind of data visualization, and the fewest colours required for to colour some class of graphs that can be drawn on a surface. (2) Probabilistic analysis using the tools of probability theory. Recent examples include the expected running-time of a point-location data structure under a random query distribution, the properties of a wireless network whose nodes are distributed uniformly in some region, and the properties of a rumour-spreading network modelled as a random tree. (3) Real performance analysis through implementation and experiments. A recent example is the study of the real-time performance, on hundreds of different systems, of classic widely-used algorithms for searching in an ordered array. The research program outlined in (1) and (2) requires a detailed study of the mathematical structures underlying these topics. As such, it uses and drives the development of new fundamental results in combinatorial geometry, graph theory, and probability theory. The research program outlined in (3) requires careful implementation and experimentation. This work helps to illuminate the often surprising nuances of modern microprocessor systems, which are exceedingly complex.