Problems in Randomized Algorithms, Random Graphs, and Computational Geometry

随机算法、随机图和计算几何中的问题

• 批准号: RGPIN-2019-04269
• 负责人: Delcourt, Michelle
• 金额: $ 2.4万
• 依托单位: Ryerson University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749563
• 关键词: Problems; Randomized; Algorithms; Random; Graphs; Problems; Randomized; Algorithms; Random; Graphs

The overarching goal of my research program is to solve a number of long standing open problems in the intersection of theoretical computer science, graph theory, and probability theory. A commonality between the proposed topics is the use of probabilistic techniques. More precisely, my proposed research program focuses on the following areas. (Objective 1) Randomized algorithms. Although counting the number of proper k-colourings of a graph is a computationally hard problem, Jerrum, Valiant, and Vazirani showed that a nearly uniform sampler gives rise to an approximate enumeration, motivating the question of finding an algorithm to efficiently generate uniformly random proper colourings of a graph; this is a central topic in both computer science and statistical physics.  My colleagues and I made a recent breakthrough, the first progress on the most important question in this area in 19 years. My students and I will push this approach further, both working on the fundamental problem for Glauber dynamics and using similar techniques to bound the mixing time of other Markov chains as well. (Objective 2) Random regular graphs. A question that has attracted much interest in graph theory is: under what conditions can we partition the edge set of a graph into edge disjoint copies of a subgraph? This is fundamentally related to some of the most notorious open areas of research such as finding orientations of certain types, nowhere-zero flows, and colourings of planar graphs. A key new insight is that moving long standing problems from structural graph theory to the random regular setting can provide additional machinery and help to shed light on classical, longstanding problems.  For instance using probabilistic techniques, a coauthor and I recently showed that a random 4-regular graph has a decomposition into 3-stars asymptotically almost surely. An important line of research with far reaching applications is generalizing this result in various ways.  My students and I will pursue developing methods for k-stars in d-regular random graphs as well as decompositions into other trees. (Objective 3) Computational geometry. An active line of inquiry in combinatorics in recent years has been extending classical results to the so-called sparse random setting, where the goal is to show that certain known properties of "dense" combinatorial structures are inherited by their randomly chosen "sparse" substructures. In this spirit my team and I will develop an algorithmic approach that shows if a given algebraic hypergraph is "dense" in a certain sense, then a generic low-dimensional subset of the vertices induces a subhypergraph that is also "dense." Such results have applications in computational geometry and matroid theory. My team and I will also establish a natural generalization of the classical dimension of fibers theorem in algebraic geometry, a result interesting in its own right.

我的研究计划的总体目标是在理论计算机科学，图形论和概率理论的交集中解决许多长期存在的开放问题。所提出的主题之间的一个共同点是使用概率技术。更确切地说，我提出的研究计划着重于以下领域。 （目标1）随机算法。尽管计算图的数量是一个计算困难的问题，但Jerrum，Valiant和Vazirani表明，几乎均匀的采样器会引起近似枚举，激发了找到算法以有效地产生图表的均匀随机的合适色彩的问题；这是计算机科学和统计物理学的核心主题。我和我的同事们最近取得了突破，这是19年来最重要问题的第一个进展。我和我的学生将进一步推动这种方法，既可以解决格劳伯动态的基本问题，又要使用类似的技术来绑定其他马尔可夫链的混合时间。 （目标2）随机常规图。一个对图理论引起极大兴趣的问题是：在什么条件下，我们可以将图的边缘集分为子图的边缘分离副本？这从根本上与一些最臭名昭著的研究领域有关，例如找到某些类型的方向，零流量和平面图的着色。一个关键的新见解是，将长期存在的问题从结构图理论转移到随机的常规设置可以提供额外的机械，并有助于阐明经典，长期存在的问题。例如，使用概率技术，合着者和我最近表明，几乎可以肯定的是，随机的4型图形分解为三星级。与遥远应用程序相关的一项重要研究是通过各种方式推广此结果。我和我的学生将追求D型随机图中K-Stars的开发方法，并将其分解为其他树木。 （目标3）计算几何形状。近年来，组合术中的一条主动询问线已被扩展到所谓的稀疏随机设置，其目标是证明某些已知的“密集”组合结构的某些已知特性是通过其随机选择的“稀疏”下结构所继承的。本着这种精神，我和我的团队将开发一种算法方法，该方法表明，给定代数超图在某种意义上是“密集”的，那么顶点的一般低维子集会诱导一个也是“密集”的亚夹纸。这些结果在计算几何学和矩形理论中有应用。我和我的团队还将建立对代数几何形状中纤维定理的经典维度的自然概括，这本身就是有趣的。