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

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

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.