¿Por qué el análisis de Fourier de las funciones booleanas "funciona"?

A lo largo de los años, me he acostumbrado a ver muchos teoremas de TCS probados mediante análisis discreto de Fourier. La transformación de Walsh-Fourier (Hadamard) es útil en prácticamente todos los subcampos de TCS, incluidas las pruebas de propiedad, pseudoaleatoriedad, complejidad de comunicación y computación cuántica.

Si bien me sentí cómodo usando el análisis de Fourier de las funciones booleanas como una herramienta muy útil cuando estoy abordando un problema, y ​​aunque tengo un presentimiento bastante bueno para qué casos usar el análisis de Fourier probablemente arrojaría algunos buenos resultados; Tengo que admitir que no estoy realmente seguro de qué es lo que hace que este cambio de base sea tan útil.

¿Alguien tiene una intuición de por qué el análisis de Fourier es tan fructífero en el estudio de TCS? ¿Por qué tantos problemas aparentemente difíciles se resuelven escribiendo la expansión de Fourier y realizando algunas manipulaciones?

Nota: mi intuición principal hasta ahora, aunque sea escasa, es que tenemos una buena comprensión de cómo se comportan los polinomios, y que la transformación de Fourier es una forma natural de ver una función como un polinomio multilineal. Pero, ¿por qué específicamente esta base? ¿Qué es tan único en la base de las paridades?

Aquí está mi punto de vista, que aprendí de Guy Kindler, aunque alguien con más experiencia probablemente pueda dar una mejor respuesta: considere el espacio lineal de funciones , y considere un operador lineal de la forma σ w (para w ∈ { 0 , 1 } n ), que asigna una función f ( x ) como arriba a la función f ( x + w $f: \{0,1\}^n\to\mathbb{R}$$\sigma_w$$w\in\{0,1\}^n$$f(x)$$f(x+w)$. En muchas de las preguntas de TCS, existe una necesidad subyacente de analizar los efectos que dichos operadores tienen sobre ciertas funciones.

Ahora, el punto es que la base de Fourier es la base que diagonaliza a todos esos operadores al mismo tiempo, lo que hace que el análisis de esos operadores sea mucho más simple. En términos más generales, la base de Fourier diagonaliza al operador de convolución, que también subyace en muchas de esas preguntas. Por lo tanto, es probable que el análisis de Fourier sea efectivo cuando sea necesario analizar esos operadores.

Por cierto, el análisis de Fourier es solo un caso especial de la teoría de la representación de grupos finitos. Esta teoría considera el espacio más general de funciones donde G es un grupo finito, y operadores de la forma σ h (para h ∈ G ) que asignan f ( x ) a f ( x ⋅ h ) , la teoría luego le permite encontrar una base que facilita el análisis de dichos operadores, aunque para grupos generales no se puede diagonalizar los operadores.$f:G\to \mathbb{C}$$G$$\sigma_h$$h\in G$$f(x)$$f(x\cdot h)$

Aquí podría haber otra versión de esta pregunta.

Suponiendo que la función pseudo booleana está limitada por k, la representación polinómica de Walsh de la función se puede descomponer en k subfunciones. Todos los términos lineales se recopilan en una subfunción, todas las interacciones por pares en una subfunción, luego las interacciones de 3 vías, etc.

Cada una de estas subfunciones es un "paisaje elemental" y, por lo tanto, cada una de las subfunciones es un vector propio de la matriz de adyacencia laplaciana (es decir, el vecindario de distancia 1 de Hamming). Cada subfunción tiene una "ecuación de onda" correspondiente del tipo que se encuentra en todos los paisajes elementales. Excepto que ahora hay k ecuaciones de onda que actúan en combinación.

Conocer las ecuaciones de onda permite caracterizar estadísticamente el espacio de búsqueda correspondiente de manera bastante precisa. Puede calcular la media y la varianza y sesgar sobre bolas de Hamming arbitrarias (exponencialmente grandes) y sobre hiperplanos arbitrarios del espacio de búsqueda.

Vea el trabajo de Peter Stadler sobre paisajes elementales.

Andrew Sutton y yo (Darrell Whitley) hemos trabajado en el uso de estos métodos para comprender y mejorar los algoritmos de búsqueda locales para la optimización pseudobooleana. Puede usar los polinomios de Walsh para identificar automáticamente los movimientos de mejora para los algoritmos de búsqueda locales. Nunca hay necesidad de enumerar aleatoriamente vecindarios del espacio de búsqueda. El análisis de Walsh puede decirle directamente dónde se encuentran los movimientos de mejora.

Una gran respuesta a esta pregunta probablemente todavía no existe porque es un área de investigación relativamente joven y muy activa. por ejemplo, el libro completo de Ingo Wegeners sobre funciones booleanas de 1987 no tiene nada sobre el tema (excepto para analizar la complejidad del circuito del DFT).

Una intuición o conjetura simple es que parece que los grandes coeficientes de Fourier de orden superior indican la presencia de subfunciones que deben tener en cuenta muchas variables de entrada y, por lo tanto, requieren muchas puertas. es decir, la expansión de Fourier es aparentemente una forma natural de medir cuantitativamente la dureza de una función booleana. No he visto esto directamente probado, pero creo que se insinúa en muchos resultados. por ejemplo, el límite inferior de Khrapchenkos puede estar relacionado con los coeficientes de Fourier. [1]

Se puede tomar prestada otra analogía aproximada de EE u otros campos de ingeniería hasta cierto punto donde el análisis de Fourier se usa ampliamente. a menudo se usa para filtros EE / procesamiento de señal . Los coeficientes de Fourier representan una "banda" particular del filtro. La historia también es que el "ruido" parece manifestarse en rangos particulares de frecuencias, por ejemplo, bajo o alto. en CS, una analogía con el "ruido" es "aleatoriedad", pero también queda claro por mucha investigación (alcanzando un hito en, por ejemplo, [4]) que la aleatoriedad es básicamente lo mismo que la complejidad. (en algunos casos, la "entropía" también aparece en el mismo contexto). El análisis de Fourier parece ser adecuado para estudiar el "ruido" incluso en entornos CS. [2]

otra intuición o imagen proviene de la teoría de votación / elección. [2,3] es útil analizar las funciones booleanas como si tuvieran subcomponentes que "voten" e influyan en el resultado. es decir, el análisis de la votación es una especie de sistema de descomposición de funciones. esto también aprovecha cierta teoría de votación que alcanzó alturas de análisis matemático y que aparentemente precede al uso de muchos análisis de Fourier de funciones booleanas.

Además, el concepto de simetría parece ser primordial en el análisis de Fourier. cuanto más "simétrica" ​​es la función, más se cancela el coeficiente de Fourier, y más "simple" es la función de calcular. pero también, cuanto más "aleatoria" y, por lo tanto, más compleja es la función, menos se cancelan los coeficientes. en otras palabras, la simetría y la simplicidad, y viceversa, la asimetría y la complejidad en la función parecen estar coordinadas de una manera que el análisis de Fourier puede medir.

[1] Sobre el análisis de Fourier de las funciones booleanas de Bernasconi, Codenotti, Simon

[2] Una breve introducción al análisis de Fourier sobre el cubo booleano (2008) por De Wolf

[3] Algunos temas sobre el análisis de las funciones booleanas por O'Donnell

[4] Pruebas naturales de Razborov y Rudich.