Pruebas de monotonicidad y la conjetura de los juegos 2 a 2

Título original:

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

Contenido del libro:

Este libro aborda dos cuestiones de la Teoría de la Complejidad: el problema de la prueba de monotonicidad y la conjetura de los juegos 2 a 2.

La prueba de monotonicidad es un problema del campo de la prueba de propiedades, considerado por primera vez por Goldreich et al. en 2000. La entrada del algoritmo es una función, y el objetivo es diseñar un comprobador que haga el menor número posible de consultas a la función, acepte funciones monótonas y rechace funciones alejadas de la monotonía con una probabilidad cercana a 1.

El primer resultado de este libro es un algoritmo esencialmente óptimo para este problema. El análisis del algoritmo se basa en gran medida en un análogo novedoso, dirigido y robusto de una desigualdad isoperimétrica booleana de Talagrand de 1993.

El teorema de las pruebas verificables probabilísticamente (PCP) es una de las piedras angulares de la informática teórica moderna. Un ámbito en el que las PCP son esenciales es el de la dureza de la aproximación. El objetivo es demostrar que algunos problemas de optimización son difíciles de resolver, incluso de forma aproximada. Se han demostrado muchos resultados de dureza de la aproximación utilizando el teorema PCP; sin embargo, para algunos problemas no se han obtenido resultados óptimos. Este libro aborda algunos de estos problemas, y en particular el problema de los juegos 2 a 2 y el problema de la cobertura de vértices.

El segundo resultado de este libro es una prueba de la conjetura de los juegos 2 a 2 (con completitud imperfecta), que implica nuevos resultados de aproximación de la dureza para problemas como la cobertura de vértices y el conjunto independiente. También sirve como prueba sólida hacia la conjetura de los juegos únicos, un notorio problema abierto relacionado en informática teórica. El núcleo de la prueba es una caracterización de pequeños conjuntos de vértices en grafos de Grassmann cuya expansión de aristas está acotada lejos de 1.