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.