On Monotonicity Testing and the 2-to-2 Games Conjecture/
Minzer, Dor
On Monotonicity Testing and the 2-to-2 Games Conjecture/ Dor Minzer. - First Edition - 1 PDF (xiv, 218pages) LuaTEX - ACM books, #49 2374-6777 ; . - ACM books - Collection 2 ; #49. .
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.
Mode of access: World Wide Web
System requirements: Adobe Acrobat Reader
3568031 9781450399692 9781450399678
10.1145/3568031 doi
On Monotonicity Testing and the 2-to-2 Games Conjecture (Computer Science)
Electronic books.
On Monotonicity Testing and the 2-to-2 Games Conjecture/ Dor Minzer. - First Edition - 1 PDF (xiv, 218pages) LuaTEX - ACM books, #49 2374-6777 ; . - ACM books - Collection 2 ; #49. .
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.
Mode of access: World Wide Web
System requirements: Adobe Acrobat Reader
3568031 9781450399692 9781450399678
10.1145/3568031 doi
On Monotonicity Testing and the 2-to-2 Games Conjecture (Computer Science)
Electronic books.