Resumen - La igualdad es mucho más débil que la comunicación de costo constante.

La igualdad es mucho más débil que la comunicación de costo constante.

2025-07-15 10:10:21

{"Mika Göös","Nathaniel Harms","Artur Riazanov"}

{cs.CC}

Este artículo investiga el poder del hashing simple, específicamente el problema de comunicación de igualdad, en la complejidad de la comunicación. Los autores demuestran un resultado sorprendente: incluso los protocolos aleatorios de costo constante no pueden ser "desrandomizados" de manera eficiente utilizando oráculos de Igualdad. **Encontrados Clave**: * **Comunicación de Costo Constante vs. Oráculos de Igualdad**: Los autores presentan un problema de comunicación con comunicación aleatoria de costo constante, pero que requiere nΩ(1) consultas determinísticas (o incluso no determinísticas) a un oráculo de Igualdad. Esto implica que BPP0 ̸⊆ PEq , donde BPP0 es la clase de problemas de costo constante aleatorios y PEq es la clase de problemas con costo de oráculo de Igualdad polinómico en log n. * **Separación de la Distancia de Hamming k**: Los autores también muestran que la comunicación de costo constante no se reduce a la jerarquía de Distancia de Hamming k, mejorando la separación entre BPP0 y Distancia de Hamming k. * **Dos Pruebas con Cinco Corolarios**: El artículo proporciona dos pruebas incomparables del resultado principal, una analítica y otra combinatorial. Estas pruebas dan lugar a varios corolarios interesantes, incluyendo: * La existencia de una función con norma espectral aproximada O(1) pero norma espectral exacta 2Ω( n). * La existencia de una función con tamaño de árbol de decisión de paridad aleatorio O(1) pero tamaño de árbol de decisión de paridad determinístico 2Ω( n). * Una mejora en la separación entre BPP y NPEq , donde NPEq es la clase de problemas con costo de oráculo de Igualdad no determinístico polinómico en log n. * Una mejora en los límites inferiores sobre NDEq (·), el costo de oráculo de Igualdad no determinístico. * **Implicaciones**: * Los resultados resaltan las limitaciones del hashing simple, incluso en presencia de oráculos de Igualdad, en la desrandomización eficiente de protocolos de comunicación. * Proporcionan nuevas perspectivas sobre la complejidad de los problemas de comunicación y el poder de diferentes tipos de oráculos. * Los corolarios tienen implicaciones para diversas áreas de la teoría de la computación, incluyendo la teoría de la complejidad, la complejidad de la comunicación y el análisis de funciones booleanas. **Significación**: Este artículo realiza contribuciones significativas al campo de la complejidad de la comunicación, proporcionando nuevas perspectivas sobre el poder del hashing simple y las limitaciones de la desrandomización utilizando oráculos de Igualdad. Los resultados tienen implicaciones para diversas áreas de la teoría de la computación y proporcionan una base para futuras investigaciones en complejidad de la comunicación y campos relacionados.