Despre testarea monotonicității și conjectura jocurilor 2 la 2

Titlul original:

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

Conținutul cărții:

Această carte discută două probleme din teoria complexității: problema testării monotonicității și conjectura jocurilor 2 la 2.

Testarea monotonicității este o problemă din domeniul testării proprietăților, considerată pentru prima dată de Goldreich et al. în 2000. Intrarea algoritmului este o funcție, iar obiectivul este de a proiecta un tester care efectuează cât mai puține interogări ale funcției, acceptă funcții monotone și respinge funcții departe de monotonie cu o probabilitate apropiată de 1.

Primul rezultat al acestei cărți este un algoritm esențial optim pentru această problemă. Analiza algoritmului se bazează în mare măsură pe un analog nou, direcționat și robust al unei inegalități izoperimetrice booleene a lui Talagrand din 1993.

Teorema probelor verificabile probabilistic (PCP) este una dintre pietrele de temelie ale informaticii teoretice moderne. Un domeniu în care PCP sunt esențiale este cel al dificultăților de aproximare. Aici, obiectivul este de a dovedi că anumite probleme de optimizare sunt greu de rezolvat, chiar și aproximativ. Multe rezultate privind dificultatea aproximării au fost demonstrate folosind teorema PCP; cu toate acestea, pentru unele probleme nu s-au obținut rezultate optime. Această carte abordează unele dintre aceste probleme, în special problema jocurilor 2 la 2 și problema acoperirii vertexurilor.

Al doilea rezultat al acestei cărți este o demonstrație a conjecturii jocurilor 2 la 2 (cu completitudine imperfectă), care implică noi rezultate de aproximare dificile pentru probleme precum acoperirea vertexurilor și setul independent. Aceasta servește, de asemenea, drept dovadă puternică pentru conjectura jocurilor unice, o problemă deschisă notorie legată de aceasta în informatica teoretică. În centrul dovezii se află o caracterizare a seturilor mici de vârfuri din grafurile Grassmann a căror expansiune a marginilor este limitată departe de 1.