Geometric Tools for Algorithms
Geometric Tools for Algorithms
批准号:
0307536
负责人:
Santosh Vempala
金额:
$10.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2003
资助国家:
美国
项目状态:
已结题
起止时间:
2003-07-01 至 2006-06-30
中文摘要
题目:算法的几何工具这个项目的目标是开发一套基于几何和随机性的通用算法工具。我们将研究四种具体的方法——几何随机漫步、凸松弛、随机投影和谱投影。每种技术都可以解决一些基本问题(即产生有效的算法)。这些包括凸优化,np困难问题的近似算法和分布的混合学习。这些问题的解决方案引出了关于这些技术的适用性和效率的几个问题(例如,随机漫步方法可以有效地采样哪些函数?计算体积的速度有多快?是否有松弛细化的方法来改善完整性差距?光谱法的局限性是什么?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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Travel: NSF Student Travel Grant for 2023 PROTRAC:Probabilistic Trajectories in Algorithms and Combinatorics
-
批准号:2340325
-
项目类别:Standard Grant
-
资助金额:$2.6万
-
财政年份:2023
-
负责人:Santosh Vempala
-
依托单位:
Collaborative Research: Foundations of Deep Learning: Theory, Robustness, and the Brain
-
批准号:2134105
-
项目类别:Standard Grant
-
资助金额:$15.0万
-
财政年份:2021
-
负责人:Santosh Vempala
-
依托单位:
Collaborative Research: AF: Medium: Fundamental Challenges in Optimization
-
批准号:2106444
-
项目类别:Continuing Grant
-
资助金额:$105.0万
-
财政年份:2021
-
负责人:Santosh Vempala
-
依托单位:
AF: Small: Fundamental High-Dimensional Algorithms
-
批准号:2007443
-
项目类别:Standard Grant
-
资助金额:$40.0万
-
财政年份:2020
-
负责人:Santosh Vempala
-
依托单位:
AF: Small: Collaborative Research: A Computational Theory of Brain Function
-
批准号:1909756
-
项目类别:Standard Grant
-
资助金额:$20.0万
-
财政年份:2019
-
负责人:Santosh Vempala
-
依托单位:
TRIPODS+X: RES: Collaborative Research: Scaling Up Descriptive Epidemiology and Metabolic Network Models via Faster Sampling
-
批准号:1839323
-
项目类别:Standard Grant
-
资助金额:$12.0万
-
财政年份:2018
-
负责人:Santosh Vempala
-
依托单位:
AF:Small: Fundamental High-Dimensional Algorithms
-
批准号:1717349
-
项目类别:Standard Grant
-
资助金额:$40.0万
-
财政年份:2017
-
负责人:Santosh Vempala
-
依托单位:
AF: Medium: Collaborative Research: The Power of Randomness for Approximate Counting
-
批准号:1563838
-
项目类别:Continuing Grant
-
资助金额:$80.0万
-
财政年份:2016
-
负责人:Santosh Vempala
-
依托单位:
AF: EAGER: Fundamental High-Dimensional Algorithms
-
批准号:1555447
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:2015
-
负责人:Santosh Vempala
-
依托单位:
EAGER: Convex Optimization Algorithms for 21st Century Challenges
-
批准号:1415498
-
项目类别:Standard Grant
-
资助金额:$30.0万
-
财政年份:2014
-
负责人:Santosh Vempala
-
依托单位:
AF: Small: Fundamental High-Dimensional Algorithms based on Convex Geometry and Spectral Methods
-
批准号:1217793
-
项目类别:Standard Grant
-
资助金额:$42.0万
-
财政年份:2012
-
负责人:Santosh Vempala
-
依托单位:
AF: Large: Collaborative Research: Random Processes and Randomized Algorithms
-
批准号:0910584
-
项目类别:Standard Grant
-
资助金额:$78.0万
-
财政年份:2009
-
负责人:Santosh Vempala
-
依托单位:
AF: Small: Fundamental Algorithms based on Convex Geometry and Spectral Methods
-
批准号:0915903
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2009
-
负责人:Santosh Vempala
-
依托单位:
Lipton Theory Symposium: A Workshop in Honor of Richard Lipton's 60th Birthday
-
批准号:0822860
-
项目类别:Standard Grant
-
资助金额:$0.6万
-
财政年份:2008
-
负责人:Santosh Vempala
-
依托单位:
Fundamental Algorithms based on Random Sampling, Convex Relaxation, and Spectral Analysis
-
批准号:0721503
-
项目类别:Standard Grant
-
资助金额:$30.0万
-
财政年份:2006
-
负责人:Santosh Vempala
-
依托单位:
Fundamental Algorithms based on Random Sampling, Convex Relaxation, and Spectral Analysis
-
批准号:0634880
-
项目类别:Standard Grant
-
资助金额:$30.0万
-
财政年份:2006
-
负责人:Santosh Vempala
-
依托单位:
ITR Collaborative Research: Models. Algorithms, and Analyses for Clustering Data
-
批准号:0312339
-
项目类别:Standard Grant
-
资助金额:$9.0万
-
财政年份:2003
-
负责人:Santosh Vempala
-
依托单位:
CAREER: Geometric Tools for Algorithms
-
批准号:9875024
-
项目类别:Continuing Grant
-
资助金额:$24.0万
-
财政年份:1999
-
负责人:Santosh Vempala
-
依托单位:
海外基金