On Monotonicity Testing and the 2-to-2 Games Conjecture/ (Record no. 397)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 03064nam a2200457 i 4500 |
| 001 - CONTROL NUMBER | |
| control field | 9781450399692 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | ACM |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20260528133339.0 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 221205s2022 nyu 001 0deng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 3568031 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9781450399692 |
| Qualifying information | ebook |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9781450399678 |
| Qualifying information | epub |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Canceled/invalid ISBN | 9781450399685 |
| Qualifying information | hardcover |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Canceled/invalid ISBN | 9781450399661 |
| Qualifying information | paperback |
| 024 7# - OTHER STANDARD IDENTIFIER | |
| Standard number or code | 10.1145/3568031 |
| Source of number or code | doi |
| 100 0# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Minzer, Dor |
| Relator term | author. |
| 245 10 - TITLE STATEMENT | |
| Title | On Monotonicity Testing and the 2-to-2 Games Conjecture/ |
| Statement of responsibility, etc. | Dor Minzer. |
| 250 ## - EDITION STATEMENT | |
| Edition statement | First Edition |
| 264 #1 - PRODUCTION, PUBLICATION, DISTRIBUTION, MANUFACTURE, AND COPYRIGHT NOTICE | |
| Place of production, publication, distribution, manufacture | [New York, NY, USA] : |
| Name of producer, publisher, distributor, manufacturer | Association for Computing Machinery; |
| Date of production, publication, distribution, manufacture, or copyright notice | [2022]. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 PDF (xiv, 218pages) |
| Other physical details | LuaTEX |
| 490 1# - SERIES STATEMENT | |
| Series statement | ACM books, |
| International Standard Serial Number | 2374-6777 ; |
| Volume/sequential designation | #49 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Acknowledgements |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 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 |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 5 The Biased Long Code and Hardness of Vertex Cover -- 5.1 Biased Long Code -- 5.2 The Reduction |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | 6 Conclusions and Open Problems |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Bibliography |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Authors' Biographies |
| 505 8# - FORMATTED CONTENTS NOTE | |
| Formatted contents note | Index |
| 506 ## - RESTRICTIONS ON ACCESS NOTE | |
| Terms governing access | Abstract freely available; full-text restricted to subscribers or individual document purchasers. |
| 530 ## - ADDITIONAL PHYSICAL FORM AVAILABLE NOTE | |
| Additional physical form available note | Also available in print. |
| 538 ## - SYSTEM DETAILS NOTE | |
| System details note | Mode of access: World Wide Web |
| 538 ## - SYSTEM DETAILS NOTE | |
| System details note | System requirements: Adobe Acrobat Reader |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name entry element | On Monotonicity Testing and the 2-to-2 Games Conjecture (Computer Science) |
| 655 #0 - INDEX TERM--GENRE/FORM | |
| Genre/form data or focus term | Electronic books. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Relationship information | Print version: |
| International Standard Book Number | 9781450399685 |
| -- | 9781450399661 |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE | |
| Uniform title | ACM books - Collection 2 ; |
| Volume/sequential designation | #49. |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Materials specified | Abstract with links to full text |
| Uniform Resource Identifier | <a href="https://doi.org/10.1145/3568031">https://doi.org/10.1145/3568031</a> |
No items available.