CAREER: Fast algorithms via a spectral theory for graphs with a prescribed cut structure

涉及非常大数据集的关键应用程序需要快速运行并提供强大性能保证的算法。在众多的例子中，有对医学扫描的分析，以及通过成像获取神经系统的连通性，这是当前计算神经科学的一个重要任务。这些问题通常是通过首先将数据建模为网络（也称为图），然后应用特定于图的算法来解决它们来解决的。在许多可能性中，依赖于图的某些代数表示的算法已经变得非常有吸引力，因为最近的理论进展使它们非常省时。然而，效率似乎是以生成的解决方案偶尔质量低劣为代价的。通过对研究这些代数表示的理论提出的扩展，该项目将设计具有强保证和广泛适用性的新算法。谱图理论研究图的代数性质和组合性质之间的联系。众所周知，这些联系远非紧密。例如，两个给定的图可能具有近似相同的切割，但特征值和特征向量明显不同。因此，图上的切问题的谱算法，虽然非常快，但不能提供很好的近似保证。这个项目将谱图理论的各个方面扩展到切点结构的谱理论，切点结构被定义为具有近似规定切点的图集。新理论的核心问题是：什么样的光谱特性可以通过给定切割结构中的图形来实现？该项目的目标是证明任何切割结构都包含其特征向量提供有关其切割的紧密信息的图。该项目还将研究这些特殊图的有效计算算法，通过本质上修改输入图的频谱而不显着改变其切割。然后，将谱修正算法与经典谱算法相结合，产生具有增强近似保证的快速算法。该项目将利用谱图理论与不经意路由算法中发现的图分解之间的联系。反过来，预计该项目也将对路由问题产生影响。在后期阶段，该项目将研究光谱修正的理论极限。它还将研究在算法和其他有趣的图类（如社会或生物网络）上的现象的表现中发展的理论的描述质量。该项目将免费传播新算法的原型实现，并将其应用于工业界和学术界的计算机视觉和机器学习问题。申请将通过选定的跨学科合作进行。理论和应用工作之间的平衡将在本科和研究生阶段为更广泛的教育努力服务，这也将包括引入新课程。这项研究的很大一部分将在波多黎各大学进行，因此预计该项目将对代表性不足的少数民族的教育产生重大影响。

Critical applications involving very large data sets require algorithms that run fast and provide strong performance guarantees. Among the numerous examples are the analysis of medical scans and the acquisition -via imaging- of connectivity in neural systems, an important task in current computational neuroscience. These problems are very often approached by first modeling the data as networks -also called graphs- and then applying graph-specific algorithms to solve them. Among many possibilities, algorithms that rely on certain algebraic representations of graphs have become very appealing due to recent theoretical progress that renders them very time-efficient. However, efficiency appears to come at the cost of an occasionally inferior quality in the generated solutions. Via the proposed extensions of the theory studying these algebraic representations, the project will design new algorithms with strong guarantees and wide applicability.Spectral graph theory studies the connections between algebraic and combinatorial properties of graphs. It is well known that these connections can be far from tight. For example, two given graphs may have approximately the same cuts, but significantly different eigenvalues and eigenvectors. As a result, spectral algorithms for cut problems on graphs, albeit very fast, do not provide good approximation guarantees. This project will extend aspects of spectral graph theory to a spectral theory for cut structures, defined as sets of graphs with approximately prescribed cuts. The central question of the new theory is: What kind of spectral properties can be realized by graphs within a given cut structure?A goal of the project is to show that any cut structure contains graphs whose eigenvectors provide tight information about its cuts. The project will also study algorithms for the efficient computation of these special graphs, by essentially modifying the spectrum of an input graph without significantly altering its cuts. Then, the combination of spectral modification and classical spectral algorithms will yield fast algorithms with enhanced approximation guarantees. The project will draw from connections of spectral graph theory with graph decompositions discovered in the context of oblivious routing algorithms. In turn, it is expected that the project will have an impact on routing problems too. In later stages the project will study the theoretical limits of spectral modification. It will also examine the descriptive quality of the developed theory in the performance of algorithms and other phenomena on interesting classes of graphs, such as social or biological networks.The project will freely disseminate prototype implementations of the new algorithms and will apply them to computer vision and machine learning problems in industry and academia. Applications will be pursued via selected interdisciplinary collaborations. The balance between theoretical and applied work will serve a broader educational effort at both the undergraduate and graduate level, which will also include the introduction of new courses. A significant part of the research will be carried out at the University of Puerto Rico, and so the project is expected to have a significant impact in the education of underrepresented minorities.