000			03064nam a2200457 i 4500
001			9781450399692
003			ACM
005			20260609133907.0
008			221205s2022 nyu 001 0deng d
020			_a3568031
020			_a9781450399692 _qebook
020			_a9781450399678 _qepub
020			_z9781450399685 _qhardcover
020			_z9781450399661 _qpaperback
024	7		_a10.1145/3568031 _2doi
100	0		_aMinzer, Dor _eauthor.
245	1	0	_aOn Monotonicity Testing and the 2-to-2 Games Conjecture/ _cDor Minzer.
250			_aFirst Edition
264		1	_a[New York, NY, USA] : _bAssociation for Computing Machinery; _c[2022].
300			_a1 PDF (xiv, 218pages) _bLuaTEX
490	1		_aACM books, _x2374-6777 ; _v#49
505	8		_aAcknowledgements
505	8		_a1 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
505	8		_a2 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
505	8		_a3 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
505	8		_a4 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
505	8		_a5 The Biased Long Code and Hardness of Vertex Cover -- 5.1 Biased Long Code -- 5.2 The Reduction
505	8		_a6 Conclusions and Open Problems
505	8		_aBibliography
505	8		_aAuthors' Biographies
505	8		_aIndex
506			_aAbstract freely available; full-text restricted to subscribers or individual document purchasers.
530			_aAlso available in print.
538			_aMode of access: World Wide Web
538			_aSystem requirements: Adobe Acrobat Reader
650		0	_aOn Monotonicity Testing and the 2-to-2 Games Conjecture (Computer Science)
655		0	_aElectronic books.
776	0	8	_iPrint version: _z9781450399685 _z9781450399661
830		0	_aACM books - Collection 2 ; _v#49.
856	4	0	_3Abstract with links to full text _uhttps://doi.org/10.1145/3568031
999			_c940 _d940