El Lovasz Local Lemma (LLL) es una herramienta probabilística que muestra que, si una colección de eventos "malos" B en un espacio de probabilidad no es demasiado probable ni demasiado interdependiente, existe una probabilidad positiva de que no sea malo. Se producen eventos en B. Moser & Tardos (2010) proporcionaron algoritmos secuenciales y paralelos que transformaron la mayoría de las aplicaciones de la asignación de variables LLL en algoritmos eficientes. Un marco de Harvey & Vondrak (2015) basado en "remuestreo de oráculos" extendió esto a algoritmos secuenciales generales para otros espacios probabilísticos que satisfacen el Lemma Local Lopsided Lovasz (LLLL).
Describimos una nueva propiedad estructural del remuestreo de oráculos que se aplica a todos los oráculos de remuestreo conocidos, que llamamos "falta de atención". significa que la interacción entre dos eventos malos B_0, B_1 depende solo de la aleatoriedad utilizada para remuestrear B, y no del estado preciso dentro de B.
Esta propiedad tiene dos consecuencias principales. Primero, es la clave para lograr un algoritmo LLLL paralelo unificado, que es más rápido que los algoritmos específicos de problemas anteriores de Harris (2016) para el algoritmo LLLL de asignación de variables y de Harris & Srinivasan (2014) para permutaciones. Este nuevo algoritmo amplía el marco de Kolmogorov (2016) y proporciona los primeros algoritmos RNC para los emparejamientos perfectos del arco iris y los ciclos hamiltonianos del arco iris de K_n.
En segundo lugar, esta propiedad nos permite crear espacios de probabilidad LLLL a partir de un conjunto de eventos "atómico" relativamente simple. Estaba intuitivamente claro que los espacios LLLL existentes se construyeron de esta manera; pero la propiedad del olvido lo formaliza. y nos da la forma de convertir automáticamente un oráculo de remuestreo para eventos atómicos en un oráculo de remuestreo para conjunciones de ellos. Al usar este marco, obtenemos el primer oráculo de remuestreo secuencial para los emparejamientos perfectos del arco iris en el hipergráfico de uniforme S completo K_n ^ {(s) }, y el primer oráculo de remuestreo conmutativo para ciclos hamiltonianos de K_n.
Sé el primero en comentar