Probabilistic Considerations in the Analysis of Algorithms

研究者将继续研究概率和算法之间的相互作用。他已经确定了这种研究的两个不同但非常重要的方面。首先，他将研究随机算法，即那些引入随机性作为加速计算手段的算法。在第二种情况下，他将考虑算法的平均情况性能。在这里，他试图解释简单算法在“典型”问题上的良好表现，而不是复杂理论的病态例子所体现的最坏情况的表现。在随机算法领域，研究者将考虑蒙特卡洛马尔可夫链算法研究中出现的问题。特别是，他将研究它们在组合计数问题和统计物理问题中的应用。他还将继续研究边缘不相交路径问题，并将众所周知的矩阵奇异值分解推广到多维矩阵。在平均案例分析领域，他将继续研究旅行推销员问题，并尝试将他的思想扩展到独立对称模型。他将继续分析计算生物学中杂交测序技术的功效。最后，他将继续研究万维网的概率模型，试图找到一个有用的模型来测试算法思想。

The investigator will continue his work on the interplay betweenprobability and algorithms. He has identified two distinct but very important aspects of such study. In the first instance he will study randomized algorithms i.e. those algorithms that introduce randomnessas a means of speeding up computation. In the second instance, he will consider the average case performance of algorithms. Here, he wants to tryto explain the good performance of simple algorithms on "typical" problems as opposed to the worst-case performance exemplified by the pathological examples of complexity theory.In the area of randomized algorithms, the investigator will considerproblems arising in the study of Monte Carlo Markov Chain algorithms.In particular he will study their use in problems associated with combinatorial counting problems and with problems in Statistical Physics. He will also continue his study of the Edge Disjoint Path problem and the construction of a generalisation of the well knownmatrix Singular Value Decomposition to multi-dimensional matrices. In the area of average case analysis, he will continue his work on theTraveling Salesman Problem and try to extend his ideas to the independent symmetric model. He will continue his work on analysing the efficacy of the Sequencing By Hybridization technique in ComputationalBiology. Finally, he will continue to work on probabilistic models of theWorld Wide Web in an attempt to find a useful model for the testing of algorithmic ideas.