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的法定任务，并被视为值得通过评估的支持。利用基金会的知识分子和更广泛的影响审查标准。