AF: Small: Fundamental High-Dimensional Algorithms based on Convex Geometry and Spectral Methods

AF：小：基于凸几何和谱方法的基本高维算法

• 批准号: 1217793
• 负责人: Santosh Vempala
• 金额: $ 42万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217793&HistoricalAwards=false
• 关键词: AF; Small; Fundamental; Dimensional; Algorithms

This project seeks to discover new algorithms and develop algorithmic tools to address fundamental open problems in the theory of algorithms under the following focus topics: (1) Rounding. The power of affine transformations in the design of algorithms and in their analysis, including for solving LP's in strongly polynomial time and approximately sandwiching convex bodies. (2) Learning. Algorithms for learning polyhedra, learning subspace juntas and identifying planted cliques in random graphs. (3) Isoperimetric inequalities. Extensions of Cheeger's method to higher eigenvalues and multi-partitions, and the KLS hyperplane conjecture. (4) Lattices and convex geometry. Optimization and sampling problems over lattices, including: (a) the complexity of integer programming (determining whether a convex body intersects a given lattice), (b) the complexity of cutting plane methods, and (c) conditions under which lattice points in a convex body be sampled efficiently.The problems explored are of a basic nature, and originate from many areas, including optimization (both discrete and continuous), sampling, machine learning and data mining. With the increasing availability of high-dimensional data in important application areas, efficient tools to handle such data are a necessity. This award addresses some of the most basic questions arising from this need. The PI, an active member of the Algorithms and Randomness Center (ARC), served as its founding director and continues in-depth collaborations with scientists from various fields to identify problems and ideas that could play a fundamental role in understanding the complexity of computation. The project will contribute to graduate courses with online notes, textbooks and up-to-date survey articles.

该项目旨在发现新的算法并开发算法工具，以解决以下重点主题下算法理论中的基本开放问题：（1）舍入。仿射转化在算法设计及其分析中的力量，包括在强烈多项式时间内解决LP和大约夹层凸体。 （2）学习。学习Polyhedra，学习子空间的术语并在随机图中识别种植的集团的算法。 （3）等等不平等。 Cheeger方法扩展到更高的特征值和多派节，以及KLS超平面猜想。 （4）晶格和凸几何。在晶格上的优化和采样问题，包括：（a）整数编程的复杂性（确定凸体是否相交给定的晶格），（b）切割平面方法的复杂性，以及（c c）在convex体内的晶格点可以有效地取样。和数据挖掘。随着重要应用领域中高维数据的可用性的增加，需要有效的工具来处理此类数据。该奖项解决了由于这种需求而引起的一些最基本的问题。 PI是算法和随机性中心（ARC）的活跃成员，是其创始董事，并继续与来自各个领域的科学家进行深入的合作，以识别可能在理解计算复杂性方面起着基本作用的问题和想法。该项目将通过在线笔记，教科书和最新的调查文章为研究生课程做出贡献。