AF: Small: Algorithms for Graph Cuts

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

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.