Efficient algorithms and data structures via geometric realizations

项目摘要：通过几何实现实现高效的算法和数据结构Assaf Naor当需要在大型数据集上执行算法任务时，理解数据中包含的海量信息的最好方法往往是将其可视化。通过将输入表示为几何对象，人们可以观察到某些有用的特征，例如数据中的簇或低维结构，并利用这些结构信息来解决手头的算法问题。近年来，通过使用现代数学中强大的方法，算法的几何设计方法得到了极大的加强。这项研究项目是数学和计算机科学的前沿课题。利用分析和几何的思想，结合现代算法方法和直觉，研究人员的研究将导致从组合优化和机器学习到信息检索和生物信息学等各种任务的中央算法原语的进展。本研究的目标是将数据嵌入到众所周知的几何对象(如欧几里得空间)中，以便保留其某些基本特征。这使得利用在执行嵌入之前不可用的直觉和方法成为可能。研究人员将开发新的数学工具，用于研究大型网络的划分和集群算法、降维技术、数据紧凑表示的构造以及快速相似性搜索和分类方法。这项拟议的研究将在广泛的领域引起计算科学家的兴趣。将加深数学和计算机科学之间的联系，以传播强大的算法设计新思想1

Abstract of project: Efficient algorithms and data structures via geometric realizationsAssaf NaorWhen one needs to perform an algorithmic task on a large data set it is often the case that the bestway to fathom the massive amount of information contained in the data is to visualize it geometrically. Byrepresenting the input as a geometric object one can observe certain helpful features, such as clusters orlow-dimensional structures within the data, and harness this structural information to solve the algorithmicproblem at hand. In recent years the geometric approach to the design of algorithms has been greatly enhancedby the use of powerful methods from modern mathematics. This research project is at the frontierboth for mathematics and computer science. Using ideas from analysis and geometry, combined with modernalgorithmic methods and intuitions, the investigator's study will lead to advances on central algorithmicprimitives for a wide variety of tasks ranging from combinatorial optimization and machine learning toinformation retrieval and bioinformatics.The goal of this research is to embed data into a well understood geometric object (such as Euclideanspace), so that certain essential features of it are preserved. This makes it possible to harness intuitions andmethods that were not available before the embedding was performed. The investigator will develop newmathematical tools for the study of algorithms for partitioning and clustering large networks, techniques fordimensionality reduction, constructions of compact representations of data, and methods for fast similaritysearch and classification. The proposed research will be of interest to computational scientists in a broadrange of areas. The connection between mathematics and computer science will be deepened in order todisseminate powerful new ideas for algorithm design.1