Random structures and algorithms

随机结构对于设计和分析解决现代问题的计算机算法很有用。它们对于理解大型复杂系统的属性也很有用，例如对等网络的链路结构。这一建议旨在继续研究一些相对较新的证明随机结构性质的技术，并开发一些非常新的技术。它将在具有基本重要性的领域推动组合数学领域的发展，目标还包括计算机科学、现实世界网络和其他当代科学领域产生的面向应用的主题。一些需要解决的问题涉及负载平衡。当将请求发送到一组处理器(或存储磁盘)时，就会出现这些问题，并且希望将请求分配给任何处理器，以便没有处理器被分配的份额超过其公平份额。其目的是展示执行分配的某些非常快速的算法通常能够非常均匀地平衡负载。其他问题与点对点网络有关。其目的是研究实践中使用的网络的理论属性，集中在从性能考虑所需的那些属性上。还有其他问题涉及随机图的进一步性质，是上述问题的抽象，其研究产生了将在这项工作中使用的那种技术。该提议的总体影响应该是解决了许多当代感兴趣的问题，并显著提高了对该领域的理解。

Random structures are useful for designing and analysing computer algorithms which solve modern-day problems. They can also be useful for understanding properties of large complex systems such as the link structure of peer-to-peer networks. This proposal aims to continue the study of some relatively new techniques for proving properties of random structures, as well as developing some very new techniques. It will advance the field of combinatorial mathematics in areas of fundamental importance, and aims also to include application-oriented topics arising from computer science, real-world networks, and other contemporary fields of science.Some of the problems to be tackled involve load balancing. These problems arise when requests are sent to a set of processors (or storage disks), and one wants to allocate the requests  such that no processor is assigned many  more than its fair share. The aim is to show that certain very fast algorithms for performing the allocation often succeed in balancing the load quite evenly. Other problems relate to peer-to-peer networks. The aim there is to study the theoretical properties of the networks used in practice, concentrating on those properties that are desirable from performance considerations. Yet other problems involve further properties of random graphs, an abstraction of the above problems whose study has yielded the sort of techniques that are to be used in this work.The overall impact of the proposal should be the solution of a number of problems of high contemporary interest, and a significant improvement of the understanding of the field.