TY  - BOOK
AU  - Minzer, Dor
TI  - On Monotonicity Testing and the 2-to-2 Games Conjecture/ 
T2  - ACM books, 
SN  - 3568031
PY  - 2022///]
CY  - [New York, NY, USA]
PB  - Association for Computing Machinery
KW  - On Monotonicity Testing and the 2-to-2 Games Conjecture (Computer Science)
KW  - Electronic books
N1  - 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; Abstract freely available; full-text restricted to subscribers or individual document purchasers; Also available in print
UR  - https://doi.org/10.1145/3568031
ER  -