On Monotonicity Testing and the 2-To-2 Games Conjecture / Dor Minzer.

Format:

Book

Author/Creator:

Minzer, Dor, author.

Series:

ACM books.

ACM Books

Language:

English

Subjects (All):

Monotone operators.

Physical Description:

1 online resource (233 p.)

Edition:

First edition.

Place of Publication:

[Place of publication not identified] : Association for Computing Machinery, 2022.

Summary:

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.

Contents:

Intro

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

Contents

Acknowledgements

1 Introduction

1.1 Monotonicity Testing (Chapter 2)

1.2 NP-hardness of 2-to-2 Games (Chapter 3)

1.2.1 Implications

1.3 Pseudo-random Sets in the Grassmann Graph Have Near-perfect Expansion (Chapter 4)

1.4 The Biased Long Code and Hardness of Vertex Cover (Chapter 5)

1.5 Open Problems (Chapter 6)

1.6 Subsequent Works

2 Monotonicity Testing and Directed Isoperimetric Inequalities

2.1 Introduction

2.1.1 Boolean Isoperimetric Type Theorems

2.1.2 Directed Analogues of Boolean Isoperimetric Type Theorems

2.1.3 Robust version of Talagrand's Theorem

2.1.4 A Robust and Directed Analogue of Talagrand's Theorem

2.1.5 Monotonicity Testing

2.1.5.1 Monotonicity Testing from Good Subgraphs

2.1.5.2 Upper Bounds on the Total Influence

2.1.5.3 Lower Bounds for Monotonicity Testing

2.1.6 Follow-up Works

2.2 Proof of Theorem 2.8

2.3 The Switch and the Split Operators

2.3.1 The Switch Operator

2.3.2 The Split Operator

2.3.3 Pure Functions

2.3.4 Splitting Only Decreases Talagrand Objective

2.4 Proof of Theorem 2.6

2.4.1 An Overview

2.4.2 The Formal Proof

2.4.2.1 Relating Splits to Switches

2.4.2.2 The Telescoping Argument

2.5 Proof of Theorem 2.9

2.6 Some Useful Results

2.6.1 A Combinatorial Fact

2.6.2 Bound on Total Influence

2.6.3 Bound on Fraction of Non-persistent Inputs

2.7 Algorithm for Monotonicity Testing

2.7.1 Existence of a Good Subgraph

2.7.2 The Tester

2.7.3 Preliminary Observations for the Analysis of the Tester

2.8 A Lower Bound for Monotonicity Testing

2.9 Additional Observations

2.9.1 Theorem 2.9 ⇒ Theorem 2.7

2.9.2 Undirected Theorems from Directed Theorems

3 NP-hardness of 2-to-2 Games

3.1 Introduction.

3.1.1 Informal Overview of the Reduction

3.1.1.1 The Inner PCP

3.1.1.2 The Outer PCP

3.1.1.3 Composition of the Outer PCP and Inner PCP

3.2 The Inner PCP: Grassmann Graph and Encoding, 2-to-2 Linearity Test, Zooming In and Out

3.2.1 The Grassmann Encoding

3.2.2 The Grassmann Linearity Test

3.2.3 Subspace Example and Zooming-in

3.2.3.1 Subspace Example

3.2.4 Salvaging Attempt: Zooming-in

3.2.5 Hyperplane Example and Zooming-out

3.2.5.1 Hyperplane Example

3.2.5.2 Zooming-out

3.3 The Outer PCP Game

3.3.1 Equation versus Variable Game

3.3.2 Smooth Equation versus Variable Game

3.3.3 Smooth Equation versus Variable Game with Advice

3.3.4 The Final Game (Outer PCP)

3.4 The Reduction to 2-to-2 Games

3.4.1 Construction of the Transitive Game G2:2

3.4.1.1 Auxiliary Lemmas

3.4.2 The Game G2:2 is a Transitive Game

3.4.3 Construction of the Final 2-to-2 Games Instance

3.4.4 Completeness

3.4.5 Setting of the Parameters

3.5 Preliminary Steps Toward Soundness Analysis

3.5.1 Covering Property

3.5.2 The Number of Successful Zoom-outs of Minimal Co-dimension is Bounded

3.5.2.1 Auxiliary Lemmas

3.5.3 Incorporating Side Condition

3.5.3.1 Grassmann Linearity Test with Side Condition

3.6 Soundness Analysis

3.6.1 Clique Consistent Assignment

3.6.2 A Strategy for the First (Larger) Prover

3.6.3 A Strategy for the Second (Smaller) Prover

3.6.4 The Success Probability of the Provers

3.6.5 Auxiliary Lemmas

3.7 "ℓ-space vs. b-space" Linearity Test

3.7.1 The ℓ-space vs. b-space Linearity Test

3.7.2 The Gowers test

3.7.3 Agreement with ℓ-spaces

3.8 Missing Proofs

3.8.1 Covering Properties

3.8.2 Proof of Lemma 3.12

3.8.3 Proof of the Upper Bound in Lemma 3.13

3.8.4 Auxiliary Lemmas and Facts.

4 Pseudo-random Sets in the Grassmann Graph Have Near-Perfect Expansion

4.1 Introduction

4.2 Preliminaries

4.2.1 The Barak-Kothari-Steurer Reduction

4.2.2 High-level Proof of Theorem 4.2

4.2.3 Switching to the Graph Hk,ℓ

4.2.4 It Suffices to Work with Hk,ℓ

4.2.5 The Eigenvectors and Eigenvalues of Hk,ℓ and Fourier Levels

4.2.6 Pseudorandomness ⇒ Low weight at Low Levels ⇒ Near-perfect Expansion

4.2.7 Lower-bounding the Fourth Moment of F=i

4.2.8 Upper-bounding the Fourth Moment of F=i

4.3 Analytic Machinery

4.3.1 High-level Perspective

4.3.2 Zoom-out Restriction Lemma

4.3.3 Defining f=r and Relating F=r, f=r and Zoom-in Densities

4.3.3.1 Defining f=r in Terms of Zoom-in Densities

4.3.3.2 Zoom-in Restriction Lemma

4.3.3.3 Some Auxiliary Lemmas

4.3.3.4 Relating F=r to Zoom-in Densities

4.3.3.5 Relating F=r and f=r

4.3.4 Relating F=r and f=r in the Fourier Domain

4.3.5 Bounding Restricted Fourier Sums of f=r

4.4 Pair-wise and Three-wise Correlations of f=i

4.4.1 Pairwise Correlations

4.4.2 Three-wise Correlations

4.5 Four-wise Correlations: Transforming the Matrices into Form

4.5.1 Removing 4-wise and 3-wise Intersections of Rowspaces

4.5.2 Getting M1, M2, M3 into Form

4.5.3 Getting M4 into Form: Part I

4.5.4 Getting M4 into Form: Part II

4.5.5 Getting M4 into Form: Part III

4.5.5.1 Step 1

4.5.5.2 Step 2

4.5.5.3 Step 3

4.6 Four-wise Correlations: A (Somewhat) Simplified Case

4.7 Four-wise Correlations: the General Case

4.A Appendix: Auxiliary Lemmas

5 The Biased Long Code and Hardness of Vertex Cover

5.1 Biased Long Code

5.1.1 Independent Sets in the Kneser graph

5.2 The Reduction

5.2.1 Completeness

5.2.2 Soundness

6 Conclusions and Open Problems

Bibliography

Author's Biography

Index.

Notes:

Description based on publisher supplied metadata and other sources.

Description based on print version record.

Includes bibliographical references and index.

ISBN:

9781450399692

145039969X