Semialgebraic Proofs and Efficient Algorithm Design

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential in the context of semi-algebraic proof systems and basic primitives in algorithm design such as linear and semidefinite programming. The proof system perspective, in this context, has provided fundamentally new tools for both algorithm design and analysis. These news tools have helped in both designing better algorithms for well-studied problems and proving tight lower bounds on such techniques.This monograph is aimed at expositing this interplay between proof systems and efficient algorithm design and surveying the state-of-the-art for two of the most important semi-algebraic proof systems: Sherali-Adams and Sum-of Squares.We rigorously develop and survey the state-of-the-art for Sherali-Adams and Sum-of-Squares both as proof systems, as well as a general family of optimization algorithms, stressing that these perspectives are formal duals to oneanother. Our treatment relies on interpreting the outputs of the Sum-of-Squares and Sherali-Adams algorithms as generalized expectation functions - a viewpoint that has been essential in obtaining both algorithmic results and lower bounds. The emphasis is on illustrating the main ideas by presenting a small fraction of representative results with detailed intuition and commentary. The monograph is self-contained and includes a review of the necessary mathematical background including basic theory of linear and semi-definite programming.

在过去的二十年中，证明系统和算法之间出现了一种令人兴奋的相互作用。一些自然的算法族可以被看作是从存在解的证明到寻找解本身的算法的一种通用转换。在半代数证明系统以及算法设计中的基本原语（如线性规划和半定规划）的背景下，这种联系可能是最重要的。在这种背景下，证明系统的观点为算法设计和分析提供了全新的工具。这些新工具既有助于为研究充分的问题设计更好的算法，也有助于证明此类技术的紧下界。 本专著旨在阐述证明系统和高效算法设计之间的这种相互作用，并综述两个最重要的半代数证明系统（Sherali - Adams和平方和）的最新研究状况。我们严谨地阐述和综述Sherali - Adams和平方和作为证明系统以及作为一类通用优化算法的最新研究状况，强调这些观点彼此是形式上的对偶。我们的论述依赖于将平方和与Sherali - Adams算法的输出解释为广义期望函数——这是在获得算法结果和下界时必不可少的一种观点。重点是通过展示一小部分具有详细直觉和注释的代表性结果来说明主要思想。本专著自成一体，包括对必要数学背景（包括线性规划和半定规划的基本理论）的回顾。