A compensated coupling bound for the average sensitivity of polynomial threshold functions

Resumen Técnico: Un Límite de Acoplamiento Compensado para la Sensibilidad Promedio de Funciones de Umbral Polinómico

Planteamiento del Problema
El artículo aborda el problema de acotar la sensibilidad promedio ($AS(f)$) de las funciones de umbral polinómico (PTF). Una PTF es una función booleana $f: \{-1, 1\}^n \to \{-1, 1\}$ definida como el signo de un polinomio real $p$ de grado como máximo $d$. La sensibilidad promedio se define como el valor esperado del número de bits de entrada que, al ser invertidos, cambian la salida de la función:
$$AS(f) = \sum_{i=1}^n P\{f(X) \neq f(X^{\oplus i})\}$$
donde $X$ es uniforme en el cubo booleano $\Omega_n$. Si bien la conjetura de Gotsman–Linial (que identifica los maximizadores simétricos exactos) ha demostrado ser falsa, la búsqueda de límites superiores uniformes ajustados sigue siendo un tema central en el análisis de funciones booleanas y la complejidad computacional. Un trabajo previo de OpenAI [1] estableció un límite de $8d\sqrt{n}$, y una nota previa de los autores refinó esto a un coeficiente uniforme de 3.83.

Metodología
Los autores refinan el argumento de "graduación ponderada" (weighted-grading) desarrollado originalmente por OpenAI [1]. Este enfoque reduce la estimación de la sensibilidad promedio a un problema de acoplamiento que involucra variables aleatorias binomiales. Las contribuciones metodológicas centrales de este artículo son:

1. Estimación de Acoplamiento Compensado: Los autores introducen un lema probabilístico refinado (Lema 2) que involucra un "acoplamiento compensado". Este lema acota el segundo momento de la diferencia entre dos variables aleatorias ($U, V$) con distribuciones idénticas y un desplazamiento acotado ($V - U \le a$). Al introducir una corrección lineal al potencial de acoplamiento, los autores eliminan la pérdida de grado al cuadrado presente en límites anteriores.
2. Estimación de Rango Finito: El artículo deriva una estimación de parámetros finitos que tiene en cuenta las dimensiones $n$ y los grados $d$ específicos, en lugar de depender únicamente de aproximaciones asintóticas.
3. Construcción de Acoplamiento Binomial: Los autores construyen acoplamientos binomiales específicos para demostrar la capacidad de ajuste de su relajación. Demuestran que el coeficiente derivado es asintóticamente ajustado para la relajación específica que utiliza solo las dos leyes marginales, la restricción de desplazamiento unilateral y la comparación de graduación de factor dos existente.

Resultos Clave
El artículo establece dos límites primarios para una función de umbral polinómico real $f$ de grado $d$ en el cubo booleano de $n$ dimensiones:

1. Límite Asintótico Uniforme:
   $$AS(f) \le \frac{8}{\sqrt{2\pi}} d\sqrt{n} \approx 3.19 d\sqrt{n}$$
   Este límite es válido uniformemente para todas las dimensiones $n$ y grados $d$.

2. Límite de Parámetro Finito Más Fuerte:
   $$AS(f) \le \min\left\{n, \frac{8 d b_n (n + d)}{n + 2d}\right\}$$
   donde $b_n = E|B_n - n/2|$ para $B_n \sim \text{Bin}(n, 1/2)$. Esta fórmula captura explícitamente la dependencia de $n$ y $d$, mostrando que el coeficiente disminuye a medida que $d$ aumenta en relación con $n$.

Los autores también demuestran que el coeficiente $8/\sqrt{2\pi}$ no puede mejorarse simplemente acotando el segundo momento sobre todos los acoplamientos con marginales binomiales y restricciones de desplazamiento, estableciendo una barrera para este enfoque de relajación específico.

Reivindicaciones y Significado
El artículo posiciona su contribución como un refinamiento del paso de probabilidad dentro del marco de graduación ponderada existente.

• Refinamiento: El trabajo mejora el coeficiente uniforme de 3.83 a $8/\sqrt{2\pi}$.
• Uniformidad: El nuevo límite es válido uniformemente en todas las dimensiones y grados, incluyendo casos donde el grado crece con la dimensión.
• Limitaciones y Modestia: Los autores declaran explícitamente que no afirman la optimalidad para las funciones de umbral polinómico en sí mismas. Clarifican que los acoplamientos construidos que demuestran la precisión del coeficiente pueden no provenir de funciones de umbral polinómico reales. Además, el artículo no pretende establecer prioridad histórica exhaustiva, revisión por pares humana independiente o una prueba formal en Lean.
• Verificación: Los resultados están respaldados por desigualdades analíticas y una extensa verificación computacional (comprobando más de 12,000 desigualdades puntuales y 8,000 pares de dimensión-grado) utilizando aritmética exacta y librerías estándar, en lugar de aproximaciones de punto flotante.

En resumen, el artículo proporciona un límite superior más ajustado y uniformemente válido para la sensibilidad promedio de las PTF mediante el refinamiento del paso de acoplamiento en el argumento de graduación ponderada, mientras delimita cuidadosamente el alcance de sus afirmaciones de optimalidad respecto a la relajación específica utilizada.