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.

Mode of access: World Wide Web

System requirements: Adobe Acrobat Reader