AF: Small: Algorithms for Graph Cuts

图在自然界和科学中无处不在，它模拟了从电信和交通网络到社会互动到生物和人工神经网络的广泛的对象和活动。不出所料，对图的算法研究已经有了很长的历史，可以追溯到计算机科学的早期；今天，图的算法被常规地用于从在线地图到医学成像到VLSI设计的各种应用中。从根本上说，图连接实体，图算法中的许多核心问题试图了解这些连接在链路故障存在的情况下是多么健壮或脆弱。该项目旨在设计更快、更简单的新算法，并帮助更好地理解图的连通性属性。新设计的算法在图像分割和可靠网络设计等领域具有重大现实影响的潜力。在教育方面，该项目将培训研究生和本科生，重点是未被充分代表的群体的参与。该项目有两个主要方面：图切割的确定性算法的设计和随机边故障下的图连通性研究。在过去的几十年里，最小割集等问题的进展在很大程度上是由新的(蒙特卡罗)随机算法的设计推动的。这些算法虽然通常非常优雅和高效，但它们的缺点是，它们提供的答案在多次运行时不一致，有时甚至是不正确的。这阻碍了它们在许多下游应用中的使用，无论是在理论上还是在实践中。该项目的第一个主旨是设计去随机化工具，帮助弥合解决基本图连通性问题的最佳随机化和确定性算法之间的差距。第二个推动力是因为观察到，在许多实际情况下，边缘故障是随机的，而不是对抗性的事件。传统的图连通性度量，例如最小割集，不能提供对网络对这种随机故障的恢复能力的真实估计。该项目旨在设计新的范例和算法来研究随机边故障网络中的连通性属性。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Graphs are ubiquitous in nature and in the sciences, and model a broad array of objects and activities ranging from telecommunication and transportation networks to social interactions to biological and artificial neural networks. Unsurprisingly, the algorithmic study of graphs has a long history tracing back to the earliest days of computer science; today, graph algorithms are routinely used in applications ranging from online maps to medical imaging to VLSI design. Fundamentally, graphs connect entities, and many of the core questions in graph algorithms seek to understand how robust or fragile these connections are in the presence of link failures. This project aims to design new algorithms that are faster, simpler, and help better understand the connectivity properties of a graph. The newly designed algorithms have the potential of significant real-world impact in areas such as image segmentation and design of reliable networks. On the educational front, the project will train graduate and undergraduate students, with an emphasis on participation of underrepresented groups.The project has two main thrusts: the design of deterministic algorithms for graph cuts and the study of graph connectivity under random edge failures. Over the last few decades, progress in problems such as minimum cut has largely been driven by the design of new (Monte Carlo) randomized algorithms. These algorithms, while often very elegant and highly efficient, suffer from the shortcoming that they provide answers that are inconsistent across multiple runs, and that are occasionally incorrect. This prevents their use in many downstream applications, both in theory and practice. The first thrust of the project is to design derandomization tools that help bridge the gap between the best randomized and deterministic algorithms for fundamental graph connectivity problems. The second thrust is motivated by the observation that in many practical scenarios, edge failures are random, rather than adversarial, events. Traditional graph connectivity measures such as minimum cuts do not provide a faithful estimate of the resilience of a network to such random failures. The project aims to design new paradigms and algorithms to study connectivity properties in networks that are subject to random edge failures.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.