Random Structures and Algorithms

这个研究项目是对离散的数学对象的研究，如网络或代码，其结构是随机生成的。长期以来，随机性在构造复杂的数学对象中扮演着重要的角色，而随机性在计算机科学的许多算法中扮演着核心角色。这项研究的一部分集中在由一系列相依的随机选择产生的对象上。这样的过程可以很好地模拟真实世界现象的动力学，比如疾病在网络中的传播，Facebook或Twitter等社交网络的演变，或者材料的相变。我们对随机结构背景下的挑战性计算问题的解决特别感兴趣，这项工作有望有助于消除复杂性理论负面结果的阴影。随机组合结构的研究已经成为离散数学的一个重要组成部分。本课题主要研究随机图和超图的各种结构性质。其中一个重点是研究各种稀疏随机图模型中哈密顿圈的存在性。人们很自然地猜测，任何确保图的最小度为3的合适的随机模型都会有高概率的哈密尔顿圈。虽然这在少数情况下已经建立，但仍然有一些非常自然的开放问题，发展稀疏随机图的哈密顿性的统一理论是本研究的长期目标。这个项目还包括对算法问题的研究。例如，我们将在杜鹃散列的研究上投入大量的精力。这里的主要问题是，将新项插入哈希表是否需要固定的预期时间。这里我们的方法是应用马尔可夫链的混合时间理论来证明关联图具有快速的混合时间。

This research project is an investigation of discrete mathematical objects, like networks or codes, whose structure is generated randomly. Randomness has long played an important role in the construction of sophisticated mathematical objects and randomness plays a central role in many algorithms in computer science. Part of this research focuses on objects that are generated by a sequence of dependent random choices. Such processes can be good models for the dynamics of real-world phenomenon, like the spread of a disease in a network, the evolution of social networks such as facebook or twitter, or phase transitions in materials. We are particularly interested in the solution of challenging computational problems in the context of random structures, and this work will hopefully be useful in drawing back the shadow of the negative results of complexity theory.The study of random combinatorial structures has emerged as an important component of Discrete Mathematics. This research project focuses on various structural properties of random graphs and hypergraphs. One area of emphasis is the study of the existence of Hamilton cycles in various sparse random graph models. It is natural to conjecture that any suitably random model that ensures that a graph has minimum degree 3 will have a Hamilton cycle with high probability. While this has been established in a few setting, a number of very natural open questions remain, and the development of a unified theory of Hamiltonicity of sparse random graphs is a long range goal of this research. This project also includes the study of algorithmic questions. For example, we will put significant effort into the study of Cuckoo hashing. Here the main question is whether or not the insertion of a new item into the hash table takes constant expected time. Our approach here will be to show that an associated graph has a fast mixing time, applying the theory of mixing times for Markov chains.