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）的演变，或者材料的相变。 我们特别感兴趣的是在随机结构的背景下，具有挑战性的计算问题的解决方案，这项工作将有望有助于拉回阴影的负面结果的复杂性theory.The随机组合结构的研究已经成为离散数学的一个重要组成部分。 本研究计画著重于随机图与超图的各种结构性质。其中一个重点领域是研究各种稀疏随机图模型中汉密尔顿圈的存在性。很自然地推测，任何适当的随机模型，确保一个图具有最小度3，将有一个汉密尔顿圈的概率很高。 虽然这已经建立在一些设置，一些非常自然的开放问题仍然存在，和稀疏随机图的Hamilton性的统一理论的发展是本研究的长期目标。 该项目还包括算法问题的研究。 例如，我们将投入大量精力研究布谷鸟哈希。 这里的主要问题是是否插入一个新的项目到哈希表需要恒定的预期时间。我们的方法在这里将表明，相关的图有一个快速的混合时间，应用马尔可夫链的混合时间理论。