Problems in Randomized Algorithms, Random Graphs, and Computational Geometry

我的研究计划的首要目标是解决理论计算机科学、图论和概率论交叉中的一些长期悬而未决的问题。拟议主题之间的一个共同点是使用概率技术。更确切地说，我提出的研究计划集中在以下几个方面。*(目标1)随机化算法。虽然计算图的真k-染色的数目是一个计算困难的问题，但Jerrum、Valiant和Vazirani证明了几乎均匀的采样器会产生近似计数，从而引发了寻找一种算法来有效地生成图的均匀随机真染色的问题；这是计算机科学和统计物理学的一个中心主题。我和我的同事们最近取得了突破，这是19年来在这一领域最重要的问题上取得的第一个进展。我和我的学生将进一步推动这一方法，他们都致力于Glauber动力学的基本问题，并使用类似的技术来限制其他马尔可夫链的混合时间。*(目标2)随机正则图。在图论中引起人们极大兴趣的一个问题是：在什么条件下，我们可以将图的边集划分为子图的边不相交的副本？这基本上与一些最臭名昭著的开放研究领域有关，例如寻找某些类型的方向、非零流和平面图的着色。一个关键的新见解是，将长期存在的问题从结构图论转移到随机规则设置可以提供额外的机制，并有助于阐明经典的、长期存在的问题。例如，使用概率技术，我和一位合著者最近证明了一个随机的4正则图几乎肯定会分解成3星。具有广泛应用的一条重要研究路线是以各种方式推广这一结果。我和我的学生将继续研究d-正则随机图中k-星的发展方法，以及分解成其他树的方法。*(目标3)计算几何。近年来，组合学中一个活跃的研究方向是将经典结果扩展到所谓的稀疏随机环境，其中的目标是证明“稠密”组合结构的某些已知性质是由其随机选择的“稀疏”子结构继承的。本着这种精神，我和我的团队将开发一种算法方法，证明如果给定的代数超图在某种意义上是“稠密的”，那么顶点的一个通用低维子集就会诱导出一个也是“稠密”的子超图。这些结果在计算几何和拟阵理论中都有应用。我和我的团队还将在代数几何中建立经典纤维维度定理的自然推广，这一结果本身就很有趣。

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.