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.