On Monotonicity Testing and the 2-To-2 Games Conjecture

This book discusses two questions in Complexity Theory: the Monotonicity Testing problem and the 2-to-2 Games Conjecture.

Monotonicity testing is a problem from the field of property testing, first considered by Goldreich et al. in 2000. The input of the algorithm is a function, and the goal is to design a tester that makes as few queries to the function as possible, accepts monotone functions and rejects far-from monotone functions with a probability close to 1.

The first result of this book is an essentially optimal algorithm for this problem. The analysis of the algorithm heavily relies on a novel, directed, and robust analogue of a Boolean isoperimetric inequality of Talagrand from 1993.

The probabilistically checkable proofs (PCP) theorem is one of the cornerstones of modern theoretical computer science. One area in which PCPs are essential is the area of hardness of approximation. Therein, the goal is to prove that some optimization problems are hard to solve, even approximately. Many hardness of approximation results were proved using the PCP theorem; however, for some problems optimal results were not obtained. This book touches on some of these problems, and in particular the 2-to-2 games problem and the vertex cover problem.

The second result of this book is a proof of the 2-to-2 games conjecture (with imperfect completeness), which implies new hardness of approximation results for problems such as vertex cover and independent set. It also serves as strong evidence towards the unique games conjecture, a notorious related open problem in theoretical computer science. At the core of the proof is a characterization of small sets of vertices in Grassmann graphs whose edge expansion is bounded away from 1.

本書討論了複雜性理論中的兩個問題：單調性測試問題和2對2遊戲猜想。

單調性測試是一個來自屬性測試領域的問題，由Goldreich等人於2000年首次提出。算法的輸入是一個函數，目標是設計一個測試器，該測試器對函數的查詢次數越少越好，並以接近1的概率接受單調函數並拒絕遠離單調的函數。

本書的第一個結果是該問題的一個基本最優算法。該算法的分析在很大程度上依賴於Talagrand於1993年提出的一個新穎、有向且強健的布林等周不等式的類比。

概率可檢查證明（PCP）定理是現代理論計算機科學的基石之一。 PCP在近似難度的領域中至關重要。在該領域中，目標是證明某些優化問題難以解決，即使是近似解。許多近似難度的結果都是使用PCP定理證明的；然而，對於某些問題，並未獲得最優結果。本書涉及其中一些問題，特別是2對2遊戲問題和頂點覆蓋問題。

本書的第二個結果是對2對2遊戲猜想（具有不完全完整性）的證明，這導致了頂點覆蓋和獨立集等問題的新近似難度結果。它也為唯一遊戲猜想提供了有力的證據，這是理論計算機科學中一個著名的相關開放問題。證明的核心是對格拉斯曼圖中邊擴張率受限的小頂點集的特徵描述。