On Monotonicity Testing and the 2-to-2 Games Conjecture

Dor Minzer

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.

Sujets

• Sciences formelles
• Mathématiques générales
• Mathématiques générales
• Computer Science
• Computers
• Informatique
• Discrete mathematics

Informations

• Publié par: Association for Computing Machinery and Morgan & Claypool Publishers
• Date de parution: 06 décembre 2022
• Nombre de lectures: 0
• EAN13: 9781450399692
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

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 analysis of the proof is a characterization of
small sets of vertices in Grassmann graphs whose edge expansion is
bounded away from 1.
ABOUT ACM BOOKS
ACM Books is a series of high-quality books
published by ACM for the computer science
community. ACM Books publications are widely
distributed in print and digital formats by major
booksellers and are available to libraries and
library consortia. Individual ACM members may access ACM
Books publications via separate annual subscription.On Monotonicity Testing and
the 2-to-2 Games ConjectureACM Books
EditorsinChief
SanjivaPrasad, Indian Institute of Technology (IIT) Delhi, India
MartaKwiatkowska, University of Oxford, UK
CharuAggarwal, IBM Corporation, USA
ACMBooksisanewseriesofhigh-qualitybooksforthecomputersciencecommunity,
publishedbyACMincollaborationwithMorgan&ClaypoolPublishers.ACMBooks
publicationsarewidelydistributedinbothprintanddigitalformatsthroughbooksellers
andtolibraries(andlibraryconsortia)andindividualACMmembersviatheACMDigital
Libraryplatform.
TheHandbookonSociallyInteractiveAgents:20yearsofResearchonEmbodied
ConversationalAgents,IntelligentVirtualAgents,andSocialRoboticsVolume2:
Interactivity,Platforms,Application
Editors:BirgitLugrin, Julius-Maximilians-Universität of Würzburg
CatherinePelachaud, CNRS-ISIR, Sorbonne Université
DavidTraum, University of Southern California
2022
EffectiveTheoriesinProgrammingPractice
JayadevMisra, The University of Texas at Austin, TX, US
2022
SpatialGems,Volume1
Editors:JohnKrumm, Microsoft Research, Microsoft Corporation, Redmond, WA, USA
AndreasZüfle, Geography and Geoinformation Science Department, George Mason University,
Fairfax, VA, USA
CyrusShahabi, Computer Science Department, University of Southern California, Los Angeles,
CA, USA
2022
EdsgerWybeDijkstra:HisLife,Work,andLegacy
Editors:KrzysztofR.Apt, CWI, Amsterdam and University of Warsaw
TonyHoare, University of Cambridge and Microsoft Research Ltd
2022
WeavingFireintoForm:AspirationsforTangibleandEmbodiedInteraction
BryggUllmer, Clemson University
OritShaer, Wellesley College
AliMazalek, Toronto Metropolitan University
CarolineHummels, Eindhoven University of Technology
2022LinkingtheWorld’sInformation:ACollectionofEssaysontheWorkofSirTim
Berners-Lee
OshaniSeneviratne, Rensselaer Polytechnic Institute
JamesA.Hendler, Rensselaer Polytechnic
2022
DemocratizingCryptography:TheWorkofWhitfieldDiffieandMartinHellman
Editor:RebeccaSlayton, Cornell University
2022
AppliedAffectiveComputing
LeiminTian, Monash University
SharonOviatt, Monash Uy
MichalMuszynski, Carnegie Mellon University and University of Geneva
BrentC.Chamberlain, Utah State Uy
JenniferHealey, Adobe Research, San Jose
AkaneSano, Rice University
2022
Circuits,Packets,andProtocols:EntrepreneursandComputerCommunications,
1968–1988
JamesL.Pelkey
AndrewL.Russell, SUNY Polytechnic Institute, New York
LoringG.Robbins
2022
TheoriesofProgramming:TheLifeandWorksofTonyHoare
Editors:CliffB.Jones, Newcastle University, UK
JayadevMisra, The University of Texas at Austin, US
2021
Software:ATechnicalHistory
KimW.Tracy, Rose-Hulman Institute of Technology, IN, USA
2021
TheHandbookonSociallyInteractiveAgents:20yearsofResearchonEmbodied
ConversationalAgents,IntelligentVirtualAgents,andSocialRobotics
Volume1:Methods,Behavior,Cognition
Editors:BirgitLugrin, Julius-Maximilians-Universität of Würzburg
CatherinePelachaud, CNRS-ISIR, Sorbonne Université
DavidTraum, University of Southern California
2021
ProbabilisticandCausalInference:TheWorksofJudeaPearl
Editors:HectorGeffner, ICREA and Universitat Pompeu Fabra
RinaDechter, University of California, Irvine
JosephY.Halpern, Cornell University
2022EventMiningforExplanatoryModeling
LalehJalali, University of California, Irvine (UCI), Hitachi America Ltd.
RameshJain, Uy of California, Irvine (UCI)
2021
IntelligentComputingforInteractiveSystemDesign:Statistics,DigitalSignal
Processing,andMachineLearninginPractice
Editors:ParisaEslambolchilar, Cardiff University, Wales, UK
AndreasKomninos, University of Patras, Greece
MarkDunlop, Strathclyde University, Scotland, UK
2021
SemanticWebfortheWorkingOntologist:EffectiveModelingforLinkedData,
RDFS,andOWL,ThirdEdition
DeanAllemang, Working Ontologist LLC
JimHendler, Rensselaer Polytechnic Institute
FabienGandon, INRIA
2020
CodeNation:PersonalComputingandtheLearntoProgramMovement
inAmerica
MichaelJ.Halvorson, Pacific Lutheran University
2020
ComputingandtheNationalScienceFoundation,1950–2016:
BuildingaFoundationforModernComputing
PeterA.Freeman, Georgia Institute of Technology
W.RichardsAdrion, University of Massachusetts Amherst
WilliamAspray, University of Colorado Boulder
2019
ProvidingSoundFoundationsforCryptography:OntheworkofShafiGoldwasser
andSilvioMicali
OdedGoldreich, Weizmann Institute of Science
2019
Concurrency:TheWorksofLeslieLamport
DahliaMalkhi, VMware Researchand Calibra
2019
TheEssentialsofModernSoftwareEngineering:FreethePracticesfromthe
MethodPrisons!
IvarJacobson, Ivar Jacobson International
Harold“Bud”Lawson, Lawson Konsult AB (deceased)
Pan-WeiNg, DBS Singapore
PaulE.McMahon, PEM Systems
MichaelGoedicke, Universität Duisburg–Essen
2019DataCleaning
IhabF.Ilyas, University of Waterloo
XuChu, Georgia Institute of Technology
2019
ConversationalUXDesign:APractitioner’sGuidetotheNaturalConversation
Framework
RobertJ.Moore, IBM Research–Almaden
RaphaelArar, IBM Researcen
2019
HeterogeneousComputing:HardwareandSoftwarePerspectives
MohamedZahran, New York University
2019
HardnessofApproximationBetweenPandNP
AviadRubinstein, Stanford University
2019
TheHandbookofMultimodal-MultisensorInterfaces,Volume3:
LanguageProcessing,Software,Commercialization,andEmergingDirections
Editors:SharonOviatt, Monash University
BjörnSchuller, Imperial College London and University of Augsburg
PhilipR.Cohen, Monash University
DanielSonntag, German Research Center for Artificial Intelligence (DFKI)
GerasimosPotamianos, University of Thessaly
‡AntonioKruger, Saarland Uy and German Research Center for Artificial
Intelligence (DFKI)
2019
MakingDatabasesWork:ThePragmaticWisdomofMichaelStonebraker
Editor:MichaelL.Brodie, Massachusetts Institute of Technology
2018
TheHandbookofMultimodal-MultisensorInterfaces,Volume2:
SignalProcessing,Architectures,andDetectionofEmotionandCognition
Editors:SharonOviatt, Monash University
BjörnSchuller, University of Augsburg and Imperial College London
PhilipR.Cohen, Monash University
DanielSonntag, German Research Center for Artificial Intelligence (DFKI)
GerasimosPotamianos, University of Thessaly
AntonioKruger‡ , Saarland Uy and German Research Center for Artificial
Intelligence (DFKI)
2018
DeclarativeLogicProgramming:Theory,Systems,andApplications
Editors:MichaelKifer, Stony Brook University
YanhongAnnieLiu, Stony Brook University
2018TheSparseFourierTransform:TheoryandPractice
HaithamHassanieh, University of Illinois at Urbana-Champaign
2018
TheContinuingArmsRace:Code-ReuseAttacksandDefenses
Editors:PerLarsen, Immunant, Inc.
Ahmad-RezaSadeghi, Technische Universität Darmstadt
2018
FrontiersofMultimediaResearch
Editor:Shih-FuChang, Columbia University
2018
Shared-MemoryParallelismCanBeSimple,Fast,andScalable
JulianShun, University of California, Berkeley
2017
ComputationalPredictionofProteinComplexesfromProteinInteraction
Networks
SriganeshSrihari, The University of Queensland Institute for Molecular Bioscience
ChernHanYong, Duke-National University of Singapore Medical School
LimsoonWong, National University of Singapore
2017
TheHandbookofMultimodal-MultisensorInterfaces,Volume1:
Foundations,UserModeling,andCommonModalityCombinations
Editors:SharonOviatt, Incaa Designs
BjörnSchuller, University of Passau and Imperial College London
PhilipR.Cohen, Voicebox Technologies
DanielSonntag, German Research Center for Artificial Intelligence (DFKI)
GerasimosPotamianos, University of Thessaly
AntonioKruger‡ , Saarland Uy and German Research Center for Artificial
Intelligence (DFKI)
2017
CommunitiesofComputing:ComputerScienceandSocietyintheACM
ThomasJ.Misa,Editor, University of Minnesota
2017
TextDataManagementandAnalysis:APracticalIntroductiontoInformation
RetrievalandTextMining
ChengXiangZhai, University of Illinois at Urbana–Champaign
SeanMassung, University of Illinois at Urbana–Champaign
2016
AnArchitectureforFastandGeneralDataProcessingonLargeClusters
MateiZaharia, Stanford University
2016