AF: Small: Probabilistic Considerations in the Analysis of Algorithms

这个项目的目的是促进对与算法设计和分析相关的概率的各个方面的理解。一般来说，这意味着随机算法的研究，算法的平均情况下的性能和相关的，看似随机的结构，如社会网络。随机算法很重要，因为它们通常是最有效的，有时是解决计算问题的唯一有效方法。对一般情况的研究揭示了为什么在最坏情况下看起来难以计算甚至难以处理的问题，可以通过简单的算法在实践中得到常规解决。研究大型现实世界网络的随机模型对于回答关于它们的算法问题和理解它们的进化是非常重要的。该项目将从平均案例分析的角度研究几个重要问题：(i)布谷鸟哈希是一种相对较新的哈希算法，尽管最近取得了重大进展，但有关其性能的一些基本问题仍未得到解答。（ii）图的匹配问题是组合优化中的五次多项式时间可解问题。它的多项式时间解是该领域的伟大成就之一。它的最坏情况复杂性，虽然多项式仍然有改进的空间，项目的目标之一是完全解决平均情况。图的hamilton环问题是典型的np困难问题之一。平均情况下的复杂性在一段时间前被减少到多项式时间，该项目的目标之一是将其减少到尽可能接近预期的线性时间。该项目还将解决涉及平均案例复杂性的其他问题。所采用的方法将涉及随机图领域的工具和技术。两个主要的工具是集中度量和集中在概率接近1的事件上。该项目还将考虑使用快速混合马尔可夫链来生成图和超图的随机着色。这一主题与统计物理学有着密切的联系，并从思想的相互交融中受益匪浅。目前仍有许多空白，特别是在超图的情况下，而该项目旨在填补这些空白。虽然图论至少有一百年的历史，但直到最近几年，图或网络的普遍性才得到如此广泛的认识。随机图的研究大约有50年的历史，需要来自该领域的技术来研究现实世界的网络。很简单，因为它们以一种看似随机的方式进化。该项目将涉及该领域的几项分析。例如，我们不知道随机图的组成结构是什么，它在优先连接下进化，但会受到删除的影响。

The aim of this project is to advance the understanding of various aspects of probability in relation to algorithm design and analysis. In general this means the study of randomized algorithms, the average case performance of algorithms and related, seemingly random, structures such as social networks. Randomized algorithms are important because they are often the most efficient and some times the only efficient way to solve computational problems. The study of the average case sheds light on why problems which in the worst-case seem computationally difficult or even intractable, can be routinely solved in practise, by simple algorithms. The research on random models of large real world networks is important for answering algorithmic questions about them and for understanding their evolution.The project will study several important problems from the point of view of average case analysis: (i) Cuckoo Hashing is a relatively new hashing algorithm and some of the basic questions about its performance remain unanswered, even though there has been significant progress of late. (ii) The matching problem for graphs is the quintissential polynomial time solvable problem in Combinatorial Optimiztion. Its polynomial time solution is one of the great achievements of the area. Its worst-case complexity, while polynomial still leaves room for improvement and one of the aims of the project is to settle the average case completely. (iii) The hamilton cycle problem for graphs is one of the canonical NP-hard problems. The average-case complexity was reduced to polynomial time some time ago and one of the aims of the project is to reduce this to as close to expected linear time as possible. The project will also several other problems involving average case complexity. The methodology employed will involve the tools and techniques from the field of Random Graphs. The two main tools being concentration of measure and concentration on events that happen with probability close to one.The project will also consider the use of Rapidly Mixing Markov Chains to generate random colorings of graphs and hypergraphs. This topic has close ties to Statistical Physics and has benefited a great deal from the cross-fertilization of ideas. There are still many gaps, particularly in the case of hypergraphs, and the project aims to close them.While graph theory is at least a hundred years old, it is only in recent years that the ubiquitousness of graphs or networks has been so widely recognized. The study of Random Graphs is about fifty years old and techniques from this area are needed to study real world networks. Simply because they evolve in a seemingly random manner. The project will involve several analyses from this area. For example, it is not known what is the component structure of a random graph, evolving under preferential attachment but subject to deletions.