AF: Small: Spectral and SDP Techniques: Average-Case Analysis and Subexponential Algorithms

AF：小：谱和 SDP 技术：平均情况分析和次指数算法

• 批准号: 1815434
• 负责人: Luca Trevisan
• 金额: $ 50万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-08-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815434&HistoricalAwards=false
• 关键词: AF; Small; Spectral; SDP; Techniques

This project involves the design and analysis of algorithms for combinatorial problems using techniques from linear algebra and convex optimization. The project bridges pure mathematics and data science, allowing new applications of mathematical ideas to the practice of computing, and from the activities on dissemination, exposition, outreach and mentoring. The project will create open-access lecture notes, surveys and blog posts, making highly technical results accessible to a broader audience. This project will play a key role in the training of graduate students, including two students belonging to underrepresented groups in computer science, and in the design of a new graduate course.The project involves novel approaches to fundamental problems, such as certifying the unsatisfiability of random constraint satisfaction problems, efficiently certifying properties of sparse random graphs and sparse random matrices, understanding the power of sub-exponential size relaxations in the sum-of-squares hierarchies, developing new construction of graph sparsifiers and finding new ways to analyze certain probabilistic distributed processes. Some of the problems in the scope of this project are not believed to admit algorithms that perform correctly and efficiently on all inputs. For this reason, the project will focus on: (a) algorithms whose running time scale "sub-exponentially" and that outperform brute-force combinatorial search, and (b) algorithms that may perform poorly on a few inputs but that perform well on average on random inputs. The second goal depends on how the inputs are distributed, and a key focus of this project is to generalize past results that apply to certain specific distributions to broader classes of distributions.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目涉及使用线性代数和凸优化技术来设计和分析组合问题的算法。该项目将纯数学和数据科学联系起来，允许数学思想在计算实践中的新应用，以及传播、阐述、推广和指导活动。该项目将创建开放获取的讲义、调查和博客文章，使更广泛的受众能够获得高技术成果。该项目将在研究生（包括两名属于计算机科学领域代表性不足群体的学生）培训以及新研究生课程的设计中发挥关键作用。该项目涉及解决基本问题的新方法，例如证明随机约束满足问题的不可满足性、有效证明稀疏随机图和稀疏随机矩阵的性质、理解平方和中次指数大小松弛的威力 层次结构，开发图稀疏器的新结构并寻找分析某些概率分布式过程的新方法。该项目范围内的一些问题不被认为允许算法在所有输入上正确有效地执行。因此，该项目将重点关注：（a）运行时间规模“次指数”且优于强力组合搜索的算法，以及（b）可能在少数输入上表现不佳但在随机输入上平均表现良好的算法。第二个目标取决于投入的分配方式，该项目的一个重点是将过去适用于某些特定分配的结果推广到更广泛的分配类别。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。