Efficient algorithms and data structures via geometric realizations

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

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