CRII: AF: New Approaches to Graph Spanners

该项目的重点是与图形空间相关的研究和教育活动。 在许多应用中，“压缩”距离信息是很重要的：如果我们给出点之间的成对距离，除了存储所有的成对距离之外，还有什么方法可以存储它们（可能会有一些损失）吗？ 这个基本的问题，可能与不同的定义“距离”，出现在各种各样的问题，如数学函数的属性测试，在计算机网络中的路由，生物医学图像分割，和许多其他.一个标准的方法来做到这一点是通过一个图形的存储，在其中我们只存储一个小的子集的距离，然后使用这些距离来（近似）推断那些我们没有存储.在过去的20年里，人们对跨度进行了广泛的研究，现在我们已经很好地描述了存储的信息量和距离估计质量之间的权衡。 在这个项目中，PI将采取一种不同的、更注重算法的观点：给定点和距离，我们能否开发出有效的算法来找到最佳的可能距离（或接近它）？从理论的角度来看，这种算法的发展将是向前迈出的重要一步，因为spatial似乎给出了数学上困难的优化问题。 它们也与网络设计中的许多其他问题有关，更好的空间算法将有望为各种相关问题带来更好的算法。 这样的算法也将是使spectrum更实用的一步，因为它们可以被用来对任何特定的输入做“我们所能做的最好的”，从而绕过许多已知的不可能的结果，这些结果只说明某些输入不能被压缩。这个项目也有一个重要的教育组成部分。 PI将开发和完善距离空间算法和近似算法的课程。 PI还将监督约翰霍普金斯大学和其他机构的本科生执行的与本项目相关的研究项目。 最后，PI将与巴尔的摩有才华的高中生合作，进行适当的项目。更正式地说，图空间是保持距离的子图，是在整个理论计算机科学中广泛使用的基本算法构建块。 绝大多数关于空间的研究都是以存在问题的形式进行的。 例如，存在哪些类型的spiritual？ 什么是实现某些参数的充分条件或必要条件？ 各种参数之间可能存在哪些折衷？虽然这些都是非常有趣的问题，但相关的优化问题却很少受到关注。 例如，如果给我们一个图，是否有一个有效的算法来找到最好的（或接近最好的）图？ 这个问题和其他相关的问题将图空间从图论领域转移到算法领域。 在这个项目中，PI将通过近似算法的透镜来研究这些优化问题。 更具体地说，在这个项目中，PI将扩展现有的基于线性规划的技术，并开发基于其他凸松弛的新技术，以设计图空间的近似算法。 这些算法将基于基于弛豫的技术（特别是Sherali-Adam LP层次和拉瑟尔SDP层次）。 与此同时，PI将设计改进的下界，包括硬度结果（通过2人1轮证明系统的新减少）和凸松弛的完整性差距。

This project is focused on research and educational activities related to graph spanners. In many applications it is important to "compress" distance information: if we are given pairwise distances between points, is there any way of storing them (possibly with some loss) other than storing all pairwise distances? This basic question, possibly with different definitions of "distances", arises in problems as diverse as property testing of mathematical functions, routing in computer networks, biomedical image segmentation, and many others.One standard way of doing this is through a graph spanner, in which we store only a small subset of the distances and then use those distances to (approximately) infer the ones that we did not store. Spanners have been studied extensively over the past 20 years, and we now have very good characterizations of what the tradeoffs are between the amount of information stored and the quality of the distance estimation. In this project the PI will take a different, more algorithmically-focused point of view: given points and distances, can we develop efficient algorithms that find the best possible spanner (or close to it)?The development of such algorithms would be a significant step forward from a theoretical point of view, as spanners seem to give mathematically difficult optimization problems. They are also related to many other problems in network design, and better algorithms for spanners will hopefully lead to better algorithms for a wide variety of related problems as well. Such algorithms would also be a step towards making spanners more practical, as they could be used to do "the best that we can" on any particular input, thus bypassing many of the known impossibility results which state only that some inputs cannot be compressed.This project also has a significant educational component. The PI will develop and refine classes on algorithms for distance spaces and approximation algorithms. The PI will also supervise research projects related to this project performed by undergraduates from Johns Hopkins and from other institutions. Finally, the PI will work with talented high school students in Baltimore on appropriate projects.More formally, graph spanners are subgraphs which preserve distances, and are a basic algorithmic building block that is used widely throughout theoretical computer science. The vast majority of research on spanners has been in the form of existential questions. For example, what types of spanners exist? What are sufficient conditions or necessary conditions to achieve certain parameters? What tradeoffs between various parameters are possible?While these are all extremely interesting questions, the related optimization questions have received much less attention. For example, if we are given a graph, is there an efficient algorithm to find the best (or close-to-best) spanner? This and other related questions move graph spanners from the realm of graph theory into the realm of algorithms. In this project the PI will study these optimization problems through the lens of approximation algorithms. More specifically, in this project the PI will extend the existing linear programming-based techniques and develop new techniques based on other convex relaxations in order to design approximation algorithms for graph spanners. These algorithms will be based on relaxation-based techniques (in particular the Sherali-Adam LP hierarchy and the Lasserre SDP hierarchy). In parallel to this, the PI will design improved lower bounds including both hardness results (through novel reductions from 2-player 1-round proof systems) and integrality gaps for convex relaxations.