Algorithms: Top to Bottom

我研究经典的计算机科学主题（算法、数据结构、网络），特别关注具有几何或图论成分的主题。我的研究项目包括理论研究和实践研究，主要从三个基本方向进行：(1)使用经典的渐近分析和组合分析工具进行最坏情况分析。最近的例子包括研究最近邻搜索算法的最坏情况运行时间，特定类型的数据可视化所需的最高分辨率，以及为可以在表面上绘制的某类图形着色所需的最少颜色。(2)运用概率论的工具进行概率分析。最近的例子包括随机查询分布下的点位置数据结构的预期运行时间，节点均匀分布在某些区域的无线网络的性质，以及随机树建模的谣言传播网络的性质。(3)通过实施和实验进行真实的性能分析。最近的一个例子是在数百个不同的系统上对经典的、广泛使用的有序数组搜索算法的实时性能进行研究。在(1)和(2)中概述的研究计划需要对这些主题的数学结构进行详细的研究。因此，它使用并推动了组合几何、图论和概率论中新的基本结果的发展。(3)中概述的研究计划需要仔细实施和实验。这项工作有助于阐明现代微处理器系统中经常令人惊讶的细微差别，这些系统非常复杂。

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.