Sui test di monotonicità e la congettura dei giochi 2 a 2

Titolo originale:

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

Contenuto del libro:

Questo libro discute due questioni di teoria della complessità: il problema della verifica della monotonicità e la congettura dei giochi 2 a 2.

Il test di monotonicità è un problema del campo dei test di proprietà, considerato per la prima volta da Goldreich et al. nel 2000. L'input dell'algoritmo è una funzione e l'obiettivo è progettare un tester che effettui il minor numero possibile di interrogazioni alla funzione, accetti funzioni monotone e rifiuti funzioni tutt'altro che monotone con una probabilità prossima a 1. Il primo risultato di questo libro è un test di monotonicità che si basa su un'analisi di un'analisi di un'immagine.

Il primo risultato di questo libro è un algoritmo essenzialmente ottimale per questo problema. L'analisi dell'algoritmo si basa su un analogo nuovo, diretto e robusto di una disuguaglianza isoperimetrica booleana di Talagrand del 1993.

Il teorema delle prove probabilistiche verificabili (PCP) è una delle pietre miliari della moderna informatica teorica. Un'area in cui le PCP sono essenziali è quella della durezza dell'approssimazione. L'obiettivo è dimostrare che alcuni problemi di ottimizzazione sono difficili da risolvere, anche in modo approssimativo. Molti risultati di durezza dell'approssimazione sono stati dimostrati utilizzando il teorema delle PCP; tuttavia, per alcuni problemi non si sono ottenuti risultati ottimali. Questo libro tratta alcuni di questi problemi, in particolare il problema dei giochi 2 a 2 e il problema della copertura dei vertici.

Il secondo risultato di questo libro è la dimostrazione della congettura dei giochi 2 a 2 (con completezza imperfetta), che implica nuovi risultati di durezza dell'approssimazione per problemi come il vertex cover e l'insieme indipendente. Inoltre, serve come prova forte per la congettura dei giochi unici, un noto problema aperto correlato nell'informatica teorica. Il fulcro della dimostrazione è una caratterizzazione di piccoli insiemi di vertici nei grafi di Grassmann la cui espansione dei bordi è limitata a 1.