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

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

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.