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.