Geometric Tools for Algorithms

标题：算法的几何工具这个项目的目标是开发一套基于几何和随机性的通用算法工具。将研究四种具体的方法--几何随机游动、凸弛豫法、随机投影法和谱投影法。每种技术都有可以解决的基本问题(即产生有效的算法)。其中包括凸优化、NP-Hard问题的近似算法和分布的学习混合。这些问题的解决方案导致了关于这些技术的适用性和效率的几个问题(例如，哪些函数可以通过随机行走方法有效地采样？计算体积的速度有多快？有没有一种松弛细化方法来改善完整性差距？光谱法的局限性是什么？)PI计划解决这些问题，并使用答案来解决算法中的基本开放问题。智力优势：几何洞察和方法在发现基本问题的多项式时间算法中发挥着越来越重要的作用。在算法领域迅速发展的同时，这些工具将在形成算法理论方面发挥关键作用，这些理论将加深我们的理解，并通过帮助解决关键的开放问题来推动该领域的发展。广泛影响：本提案着手探索的问题是基本性质的，来自不同的领域，包括组合优化、机器学习、信息检索和欧几里德几何。这些问题的进展，除了其潜在的实际影响，肯定会解开组合/几何结构，并可能产生新的分析工具。研究结果将构成一门组合优化本科课程和两门研究生课程的基础；所有这些课程的课程笔记都将在网上提供。

Title: Geometric Tools for AlgorithmsThe goal of this project is to develop a set of general algorithmic toolsbased on geometry and randomness. Four specific approaches will beinvestigated -- geometric random walks, convex relaxations, randomprojection and spectral projection. There are basic problems that can besolved by each technique (i.e., yielding efficient algorithms). Theseinclude convex optimization, approximation algorithms for NP-hard problemsand learning mixtures of distributions. The solutions to these problemslead to several questions about the applicability and efficiency of thesetechniques (e.g. What functions can be sampled efficiently by the randomwalk approach? How quickly can the volume be computed? Is there arelaxation refinement method that improves the integrality gap? What arethe limits of the spectral method?). The PI plans to address thesequestions and use the answers to tackle basic open problems in algorithms.Intellectual merit:Geometric insights and approaches play an increasingly central role in thediscovery of polynomial-time algorithms for fundamental problems. At atime when the field of algorithms is growing rapidly, such tools will becrucial in crystallizing a theory of algorithms that will deepen ourunderstanding as well as advance the field by aiding in the solution ofkey open problems.Broad impact:The problems this proposal sets out to explore are of a basic nature, andoriginate from a variety of areas, including combinatorial optimization,machine learning, information retrieval, and Euclidean geometry. Progresson these problems, in addition to its potential practical impact, is sureto unravel combinatorial/geometric structure, and is likely to yield newanalysis tools. The research results will form the basis of anundergraduate course on combinatorial optimization as well as two graduatecourses; course notes for all of these will be available online.