On Monotonicity Testing and the 2-to-2 Games Conjecture
Saved in:
| Title: | On Monotonicity Testing and the 2-to-2 Games Conjecture |
|---|---|
| Description: | This book discusses two questions in Complexity Theory: the Monotonicity Testing problem and the 2-to-2 Games Conjecture.Monotonicity testing is a problem from the field of property testing, first considered by Goldreich et al. in 2000. The input of the algorithm is a function, and the goal is to design a tester that makes as few queries to the function as possible, accepts monotone functions and rejects far-from monotone functions with a probability close to 1.The first result of this book is an essentially optimal algorithm for this problem. The analysis of the algorithm heavily relies on a novel, directed, and robust analogue of a Boolean isoperimetric inequality of Talagrand from 1993.The probabilistically checkable proofs (PCP) theorem is one of the cornerstones of modern theoretical computer science. One area in which PCPs are essential is the area of hardness of approximation. Therein, the goal is to prove that some optimization problems are hard to solve, even approximately. Many hardness of approximation results were proved using the PCP theorem; however, for some problems optimal results were not obtained. This book touches on some of these problems, and in particular the 2-to-2 games problem and the vertex cover problem.The second result of this book is a proof of the 2-to-2 games conjecture (with imperfect completeness), which implies new hardness of approximation results for problems such as vertex cover and independent set. It also serves as strong evidence towards the unique games conjecture, a notorious related open problem in theoretical computer science. At the core of the proof is a characterization of small sets of vertices in Grassmann graphs whose edge expansion is bounded away from 1. |
| Authors: | Dor Minzer |
| Resource Type: | eBook. |
| Subjects: | Monotone operators--Testing |
| Categories: | COMPUTERS / Computer Science, MATHEMATICS / Discrete Mathematics, MATHEMATICS / Mathematical Analysis |
| Database: | eBook Collection (EBSCOhost) |
| FullText | Links: – Type: ebook-pdf – Type: ebook-epub Text: Availability: 0 |
|---|---|
| Header | DbId: nlebk DbLabel: eBook Collection (EBSCOhost) An: 3766609 RelevancyScore: 1110 AccessLevel: 6 PubType: eBook PubTypeId: ebook PreciseRelevancyScore: 1109.74133300781 |
| IllustrationInfo | |
| ImageInfo | – Size: thumb Target: https://rps2images.ebscohost.com/rpsweb/othumb?id=NL$3766609$PDF&s=r – Size: medium Target: https://rps2images.ebscohost.com/rpsweb/othumb?id=NL$3766609$PDF&s=d |
| Items | – Name: Title Label: Title Group: Ti Data: On Monotonicity Testing and the 2-to-2 Games Conjecture – Name: Abstract Label: Description Group: Ab Data: This book discusses two questions in Complexity Theory: the Monotonicity Testing problem and the 2-to-2 Games Conjecture.Monotonicity testing is a problem from the field of property testing, first considered by Goldreich et al. in 2000. The input of the algorithm is a function, and the goal is to design a tester that makes as few queries to the function as possible, accepts monotone functions and rejects far-from monotone functions with a probability close to 1.The first result of this book is an essentially optimal algorithm for this problem. The analysis of the algorithm heavily relies on a novel, directed, and robust analogue of a Boolean isoperimetric inequality of Talagrand from 1993.The probabilistically checkable proofs (PCP) theorem is one of the cornerstones of modern theoretical computer science. One area in which PCPs are essential is the area of hardness of approximation. Therein, the goal is to prove that some optimization problems are hard to solve, even approximately. Many hardness of approximation results were proved using the PCP theorem; however, for some problems optimal results were not obtained. This book touches on some of these problems, and in particular the 2-to-2 games problem and the vertex cover problem.The second result of this book is a proof of the 2-to-2 games conjecture (with imperfect completeness), which implies new hardness of approximation results for problems such as vertex cover and independent set. It also serves as strong evidence towards the unique games conjecture, a notorious related open problem in theoretical computer science. At the core of the proof is a characterization of small sets of vertices in Grassmann graphs whose edge expansion is bounded away from 1. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Dor+Minzer%22">Dor Minzer</searchLink> – Name: TypePub Label: Resource Type Group: TypPub Data: eBook. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Monotone+operators--Testing%22">Monotone operators--Testing</searchLink> – Name: SubjectBISAC Label: Categories Group: Su Data: <searchLink fieldCode="ZK" term="%22COMPUTERS+%2F+Computer+Science%22">COMPUTERS / Computer Science</searchLink><br /><searchLink fieldCode="ZK" term="%22MATHEMATICS+%2F+Discrete+Mathematics%22">MATHEMATICS / Discrete Mathematics</searchLink><br /><searchLink fieldCode="ZK" term="%22MATHEMATICS+%2F+Mathematical+Analysis%22">MATHEMATICS / Mathematical Analysis</searchLink> |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=nlebk&AN=3766609 |
| RecordInfo | BibRecord: BibEntity: Classifications: – Code: 519.81 Scheme: ddc Type: prePub Languages: – Code: eng Text: English Subjects: – SubjectFull: Monotone operators--Testing Type: general Titles: – TitleFull: On Monotonicity Testing and the 2-to-2 Games Conjecture Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Dor Minzer – PersonEntity: Name: NameFull: Dor Minzer IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Type: published Y: 2022 – D: 22 M: 05 Type: profile Y: 2024 Identifiers: – Type: isbn-print Value: 9781450399661 – Type: isbn-electronic Value: 9781450399678 – Type: isbn-electronic Value: 9781450399692 Titles: – TitleFull: On Monotonicity Testing and the 2-to-2 Games Conjecture Type: main |
| ResultId | 1 |
