Random Structures and Algorithms

随机结构和算法

• 批准号: 1362785
• 负责人: ALAN FRIEZE
• 金额: $ 33万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-06-01 至 2017-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1362785&HistoricalAwards=false
• 关键词: Random; Structures; Algorithms

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.

该研究项目是对离散数学对象（例如网络或代码）的研究，其结构是随机生成的。 长期以来，随机性在复杂数学对象的构造中发挥着重要作用，并且随机性在计算机科学的许多算法中发挥着核心作用。 这项研究的一部分重点关注由一系列相关随机选择生成的对象。 这些过程可以成为现实世界现象动态的良好模型，例如疾病在网络中的传播、社交网络（例如 Facebook 或 Twitter）的演化，或者材料的相变。 我们对随机结构背景下具有挑战性的计算问题的解决特别感兴趣，这项工作有望有助于消除复杂性理论负面结果的阴影。随机组合结构的研究已成为一个重要组成部分离散数学。 该研究项目重点研究随机图和超图的各种结构特性。重点领域之一是研究各种稀疏随机图模型中汉密尔顿循环的存在性。很自然地推测，任何确保图具有最小度 3 的适当随机模型都将具有高概率的汉密尔顿循环。 虽然这已经在一些情况下得到了证实，但仍然存在许多非常自然的开放问题，并且发展稀疏随机图的哈密顿性统一理论是这项研究的长期目标。 该项目还包括算法问题的研究。 例如，我们将投入大量精力来研究 Cuckoo 哈希。 这里的主要问题是向哈希表中插入新项是否需要恒定的预期时间。我们在这里的方法是应用马尔可夫链的混合时间理论来证明关联图具有快速的混合时间。