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

Format:

Book

Author/Creator:

Minzer, Dor, author.

Series:

ACM books - Collection 2 ; #49.

ACM books, 2374-6777 ; #49

Language:

English

Subjects (All):

On Monotonicity Testing and the 2-to-2 Games Conjecture (Computer Science).

Genre:

Electronic books.

Physical Description:

1 online resource (xiv, 218pages) LuaTEX

Edition:

First Edition

Place of Publication:

[New York, NY, USA] : Association for Computing Machinery; [2022].

System Details:

Mode of access: World Wide Web

System requirements: Adobe Acrobat Reader

Contents:

Acknowledgements

1 Introduction Monotonicity Testing (Chapter 2)

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

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.2 Proof of Theorem 2.8

2.3 The Switch and the Split Operators

2.4 Proof of Theorem 2.6

2.5 Proof of Theorem 2.9

2.6 Some Useful Results

2.7 Algorithm for Monotonicity Testing

2.8 A Lower Bound for Monotonicity Testing

2.9 Additional Observations

3 NP-hardness of 2-to-2 Games

3.1 Introduction

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

3.3 The Outer PCP Game

3.4 The Reduction to 2-to-2 Games

3.5 Preliminary Steps Toward Soundness Analysis

3.6 Soundness Analysis

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

3.8 Missing Proofs

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

4.1 Introduction

4.2 Preliminaries

4.3 Analytic Machinery

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

4.5 Four-wise Correlations: Transforming the Matrices into Form

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.2 The Reduction

6 Conclusions and Open Problems

Bibliography

Authors' Biographies

Index

Other Format:

Print version:

ISBN:

3568031

9781450399692

9781450399678

Access Restriction:

Restricted for use by site license.