Análisis de funciones booleanas

Estudio de funciones booleanas mediante análisis discreto de Fourier

En matemáticas y ciencias de la computación teóricas , el análisis de funciones booleanas es el estudio de funciones de valor real en o (tales funciones a veces se conocen como funciones pseudobooleanas ) desde una perspectiva espectral. ^[1] Las funciones estudiadas son a menudo, pero no siempre, de valor booleano, lo que las convierte en funciones booleanas . El área ha encontrado muchas aplicaciones en combinatoria , teoría de elección social , gráficos aleatorios y ciencias de la computación teóricas, especialmente en dificultad de aproximación , pruebas de propiedades y aprendizaje PAC . ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle \{-1,1\}^{n}}$

Conceptos básicos

Consideraremos principalmente funciones definidas en el dominio . A veces es más conveniente trabajar con el dominio en su lugar. Si se define en , entonces la función correspondiente definida en es ${\displaystyle \{-1,1\}^{n}}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle f}$ ${\displaystyle \{-1,1\}^{n}}$ ${\displaystyle \{0,1\}^{n}}$

${\displaystyle f_{01}(x_{1},\ldots ,x_{n})=f((-1)^{x_{1}},\ldots ,(-1)^{x_{n}}).}$

De manera similar, para nosotros una función booleana es una función con valor , aunque a menudo es más conveniente considerar funciones con valor . ${\displaystyle \{-1,1\}}$ ${\displaystyle \{0,1\}}$

Expansión de Fourier

Cada función de valor real tiene una expansión única como polinomio multilineal: ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle f(x)=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}(x),\quad \chi _{S}(x)=\prod _{i\in S}x_{i}.}$

(Tenga en cuenta que incluso si la función tiene un valor de 0 a 1, esta no es una suma módulo 2, sino simplemente una suma ordinaria de números reales).

Esta es la transformada de Hadamard de la función , que es la transformada de Fourier en el grupo . Los coeficientes se conocen como coeficientes de Fourier y la suma total se conoce como la expansión de Fourier de . Las funciones se conocen como caracteres de Fourier y forman una base ortonormal para el espacio de todas las funciones sobre , con respecto al producto interno . ${\displaystyle f}$ ${\displaystyle \mathbb {Z} _{2}^{n}}$ ${\displaystyle {\hat {f}}(S)}$ ${\displaystyle f}$ ${\displaystyle \chi _{S}}$ ${\displaystyle \{-1,1\}^{n}}$ ${\displaystyle \langle f,g\rangle =2^{-n}\sum _{x\in \{-1,1\}^{n}}f(x)g(x)}$

Los coeficientes de Fourier se pueden calcular utilizando un producto interno:

${\displaystyle {\hat {f}}(S)=\langle f,\chi _{S}\rangle .}$

En particular, esto demuestra que , donde el valor esperado se toma con respecto a la distribución uniforme sobre . La identidad de Parseval establece que ${\displaystyle {\hat {f}}(\emptyset )=\operatorname {E} [f]}$ ${\displaystyle \{-1,1\}^{n}}$

${\displaystyle \|f\|^{2}=\operatorname {E} [f^{2}]=\sum _{S}{\hat {f}}(S)^{2}.}$

Si omitimos , entonces obtenemos la varianza de : ${\displaystyle S=\emptyset }$ ${\displaystyle f}$

${\displaystyle \operatorname {Var} [f]=\sum _{S\neq \emptyset }{\hat {f}}(S)^{2}.}$

Grados de Fourier y niveles de Fourier

El grado de una función es el máximo tal que para un conjunto de tamaño . En otras palabras, el grado de es su grado como polinomio multilineal. ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$ ${\displaystyle d}$ ${\displaystyle {\hat {f}}(S)\neq 0}$ ${\displaystyle S}$ ${\displaystyle d}$ ${\displaystyle f}$

Es conveniente descomponer la expansión de Fourier en niveles : el coeficiente de Fourier está en el nivel . ${\displaystyle {\hat {f}}(S)}$ ${\displaystyle |S|}$

La parte de grado ${\displaystyle d}$ es ${\displaystyle f}$

${\displaystyle f^{=d}=\sum _{|S|=d}{\hat {f}}(S)\chi _{S}.}$

Se obtiene poniendo a cero todos los coeficientes de Fourier que no estén en el nivel . ${\displaystyle f}$ ${\displaystyle d}$

Definimos de manera similar . ${\displaystyle f^{>d},f^{<d},f^{\geq d},f^{\leq d}}$

Influencia

La influencia 'ésima de una función se puede definir de dos maneras equivalentes: ${\displaystyle i}$ ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle {\begin{aligned}&\operatorname {Inf} _{i}[f]=\operatorname {E} \left[\left({\frac {f-f^{\oplus i}}{2}}\right)^{2}\right]=\sum _{S\ni i}{\hat {f}}(S)^{2},\\[5pt]&f^{\oplus i}(x_{1},\ldots ,x_{n})=f(x_{1},\ldots ,x_{i-1},-x_{i},x_{i+1},\ldots ,x_{n}).\end{aligned}}}$

Si es booleano, entonces es la probabilidad de que al invertir la coordenada 'ésima se invierta el valor de la función: ${\displaystyle f}$ ${\displaystyle \operatorname {Inf} _{i}[f]}$ ${\displaystyle i}$

${\displaystyle \operatorname {Inf} _{i}[f]=\Pr[f(x)\neq f^{\oplus i}(x)].}$

Si entonces no depende de la coordenada 'ésima. ${\displaystyle \operatorname {Inf} _{i}[f]=0}$ ${\displaystyle f}$ ${\displaystyle i}$

La influencia total de es la suma de todas sus influencias: ${\displaystyle f}$

${\displaystyle \operatorname {Inf} [f]=\sum _{i=1}^{n}\operatorname {Inf} _{i}[f]=\sum _{S}|S|{\hat {f}}(S)^{2}.}$

La influencia total de una función booleana es también la sensibilidad media de la función. La sensibilidad de una función booleana en un punto dado es el número de coordenadas tales que si invertimos la coordenada 'ésima, el valor de la función cambia. El valor medio de esta cantidad es exactamente la influencia total. ${\displaystyle f}$ ${\displaystyle i}$ ${\displaystyle i}$

La influencia total también se puede definir utilizando el Laplaciano discreto del gráfico de Hamming , adecuadamente normalizado: . ${\displaystyle \operatorname {Inf} [f]=\langle f,Lf\rangle }$

Una forma generalizada de influencia es la influencia -estable, definida por: ${\displaystyle \rho }$

${\displaystyle \operatorname {Inf} _{i}^{\,(\rho )}[f]=\operatorname {Stab} _{\rho }[\operatorname {D} _{i}f]=\sum _{S\ni i}\rho ^{|S|-1}{\hat {f}}(S)^{2}.}$

Las influencias totales correspondientes son

${\displaystyle \operatorname {I} ^{(\rho )}[f]={\frac {d}{d\rho }}\operatorname {Stab} _{\rho }[f]=\sum _{S}|S|\rho ^{|S|-1}{\hat {f}}(S)^{2}.}$

Se puede demostrar que una función tiene como máximo “constantemente” muchas coordenadas “establemente influyentes”: ${\displaystyle f:\{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle |\{i\in [n]:\operatorname {Inf} _{i}^{\,(1-\delta )}[f]\geq \epsilon \}|\leq {\frac {1}{\delta \epsilon }}.}$

Estabilidad del ruido

Dado , decimos que dos vectores aleatorios están -correlacionados si las distribuciones marginales de son uniformes, y . Concretamente, podemos generar un par de variables aleatorias -correlacionadas eligiendo primero de manera uniforme al azar y luego eligiendo de acuerdo con una de las dos reglas equivalentes siguientes, aplicadas independientemente a cada coordenada: ${\displaystyle -1\leq \rho \leq 1}$ ${\displaystyle x,y\in \{-1,1\}^{n}}$ ${\displaystyle \rho }$ ${\displaystyle x,y}$ ${\displaystyle \operatorname {E} [x_{i}y_{i}]=\rho }$ ${\displaystyle \rho }$ ${\displaystyle x,z\in \{-1,1\}^{n}}$ ${\displaystyle y}$

${\displaystyle y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}\quad {\text{or}}\quad y_{i}={\begin{cases}x_{i}&{\text{w.p. }}{\frac {1+\rho }{2}},\\-x_{i}&{\text{w.p. }}{\frac {1-\rho }{2}}.\end{cases}}}$

Denotamos esta distribución por . ${\displaystyle y\sim N_{\rho }(x)}$

La estabilidad del ruido de una función se puede definir de dos formas equivalentes: ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$ ${\displaystyle \rho }$

${\displaystyle \operatorname {Stab} _{\rho }[f]=\operatorname {E} _{x;y\sim N_{\rho }(x)}[f(x)f(y)]=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)^{2}.}$

Para , la sensibilidad al ruido de at es ${\displaystyle 0\leq \delta \leq 1}$ ${\displaystyle f}$ ${\displaystyle \delta }$

${\displaystyle \operatorname {NS} _{\delta }[f]={\frac {1}{2}}-{\frac {1}{2}}\operatorname {Stab} _{1-2\delta }[f].}$

Si es booleano, entonces esta es la probabilidad de que el valor de cambie si invertimos cada coordenada con probabilidad , independientemente. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \delta }$

Operador de ruido

El operador de ruido es un operador que toma una función y devuelve otra función dada por ${\displaystyle T_{\rho }}$ ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$ ${\displaystyle T_{\rho }f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle (T_{\rho }f)(x)=\operatorname {E} _{y\sim N_{\rho }(x)}[f(y)]=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)\chi _{S}.}$

Cuando , el operador de ruido también se puede definir utilizando una cadena de Markov de tiempo continuo en la que cada bit se invierte de forma independiente con una tasa de 1. El operador corresponde a ejecutar esta cadena de Markov para pasos que comienzan en , y toman el valor promedio de en el estado final. Esta cadena de Markov se genera mediante el laplaciano del gráfico de Hamming, y esto relaciona la influencia total con el operador de ruido. ${\displaystyle \rho >0}$ ${\displaystyle T_{\rho }}$ ${\displaystyle {\frac {1}{2}}\log {\frac {1}{\rho }}}$ ${\displaystyle x}$ ${\displaystyle f}$

La estabilidad del ruido se puede definir en términos del operador de ruido: . ${\displaystyle \operatorname {Stab} _{\rho }[f]=\langle f,T_{\rho }f\rangle }$

Hipercontractividad

Para , la -norma de una función está definida por ${\displaystyle 1\leq q<\infty }$ ${\displaystyle L_{q}}$ ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle \|f\|_{q}={\sqrt[{q}]{\operatorname {E} [|f|^{q}]}}.}$

También definimos ${\displaystyle \|f\|_{\infty }=\max _{x\in \{-1,1\}^{n}}|f(x)|.}$

El teorema de hipercontractividad establece que para cualquier y , ${\displaystyle q>2}$ ${\displaystyle q'=1/(1-1/q)}$

${\displaystyle \|T_{\rho }f\|_{q}\leq \|f\|_{2}\quad {\text{and}}\quad \|T_{\rho }f\|_{2}\leq \|f\|_{q'}.}$

La hipercontractividad está estrechamente relacionada con las desigualdades logarítmicas de Sobolev del análisis funcional . ^[2]

Un resultado similar se conoce como hipercontractividad inversa . ^[3] ${\displaystyle q<2}$

pag-Análisis sesgado

En muchas situaciones, la entrada a la función no se distribuye uniformemente sobre , sino que tiene un sesgo hacia o . En estas situaciones, es habitual considerar funciones sobre el dominio . Para , la medida con sesgo p está dada por ${\displaystyle \{-1,1\}^{n}}$ ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle 0<p<1}$ ${\displaystyle \mu _{p}}$

${\displaystyle \mu _{p}(x)=p^{\sum _{i}x_{i}}(1-p)^{\sum _{i}(1-x_{i})}.}$

Esta medida se puede generar eligiendo cada coordenada independientemente como 1 con probabilidad y 0 con probabilidad . ${\displaystyle p}$ ${\displaystyle 1-p}$

Los caracteres clásicos de Fourier ya no son ortogonales respecto de esta medida. En su lugar, utilizamos los siguientes caracteres:

${\displaystyle \omega _{S}(x)=\left({\sqrt {\frac {p}{1-p}}}\right)^{|\{i\in S:x_{i}=0\}|}\left(-{\sqrt {\frac {1-p}{p}}}\right)^{|\{i\in S:x_{i}=1\}|}.}$

La expansión de Fourier con sesgo p de es la expansión de como una combinación lineal de caracteres con sesgo p : ${\displaystyle f}$ ${\displaystyle f}$

${\displaystyle f=\sum _{S\subseteq [n]}{\hat {f}}(S)\omega _{S}.}$

Podemos extender las definiciones de influencia y del operador de ruido a la configuración p -sesgada utilizando sus definiciones espectrales.

Influencia

La influencia de está dada por ${\displaystyle i}$

${\displaystyle \operatorname {Inf} _{i}[f]=\sum _{S\ni i}{\hat {f}}(S)^{2}=p(1-p)\operatorname {E} [(f-f^{\oplus i})^{2}].}$

La influencia total es la suma de las influencias individuales:

${\displaystyle \operatorname {Inf} [f]=\sum _{i=1}^{n}\operatorname {Inf} _{i}[f]=\sum _{S}|S|{\hat {f}}(S)^{2}.}$

Operador de ruido

Se puede obtener un par de variables aleatorias correlacionadas eligiendo independientemente y , donde viene dado por ${\displaystyle \rho }$ ${\displaystyle x,z\sim \mu _{p}}$ ${\displaystyle y\sim N_{\rho }(x)}$ ${\displaystyle N_{\rho }}$

${\displaystyle y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}}$

El operador de ruido viene dado entonces por

${\displaystyle (T_{\rho }f)(x)=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)\omega _{S}(x)=\operatorname {E} _{y\sim N_{\rho }(x)}[f(y)].}$

Usando esto podemos definir la estabilidad del ruido y la sensibilidad al ruido, como antes.

Fórmula de Russo-Margulis

La fórmula de Russo-Margulis (también llamada fórmula de Margulis-Russo ^[1] ) establece que para funciones booleanas monótonas , ${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$

${\displaystyle {\frac {d}{dp}}\operatorname {E} _{x\sim \mu _{p}}[f(x)]={\frac {\operatorname {Inf} [f]}{p(1-p)}}=\sum _{i=1}^{n}\Pr[f\neq f^{\oplus i}].}$

Tanto la influencia como las probabilidades se toman con respecto a , y en el lado derecho tenemos la sensibilidad promedio de . Si pensamos en como una propiedad, entonces la fórmula establece que a medida que varía, la derivada de la probabilidad de que ocurra en es igual a la sensibilidad promedio en . ${\displaystyle \mu _{p}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle p}$ ${\displaystyle f}$ ${\displaystyle p}$ ${\displaystyle p}$

La fórmula de Russo-Margulis es clave para demostrar teoremas de umbral agudo como el de Friedgut.

Espacio gaussiano

Uno de los resultados más profundos en el área, el principio de invariancia, conecta la distribución de funciones en el cubo de Boole con su distribución en el espacio gaussiano , que es el espacio dotado de la medida gaussiana de dimensión estándar . ${\displaystyle \{-1,1\}^{n}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle n}$

Muchos de los conceptos básicos del análisis de Fourier en el cubo de Boole tienen equivalentes en el espacio gaussiano:

• La contraparte de la expansión de Fourier en el espacio gaussiano es la expansión de Hermite, que es una expansión a una suma infinita (que converge en ) de polinomios de Hermite multivariados . ${\displaystyle L^{2}}$
• La contraparte de la influencia total o sensibilidad promedio de la función indicadora de un conjunto es el área de superficie gaussiana, que es el contenido de Minkowski del límite del conjunto.
• La contraparte del operador de ruido es el operador de Ornstein-Uhlenbeck (relacionado con la transformada de Mehler ), dado por , o alternativamente por , donde es un par de gaussianas estándar correlacionadas. ${\displaystyle (U_{\rho }f)(x)=\operatorname {E} _{z\sim N(0,1)}[f(\rho x+{\sqrt {1-\rho ^{2}}}z)]}$ ${\displaystyle (U_{\rho }f)(x)=\operatorname {E} [f(y)]}$ ${\displaystyle x,y}$ ${\displaystyle \rho }$
• La hipercontractividad también se cumple (con los parámetros apropiados) en el espacio gaussiano.

El espacio gaussiano es más simétrico que el cubo booleano (por ejemplo, es invariante en cuanto a rotación) y admite argumentos continuos que pueden resultar más difíciles de obtener en el contexto discreto del cubo booleano. El principio de invariancia vincula ambos contextos y permite deducir resultados en el cubo booleano a partir de los resultados en el espacio gaussiano.

Resultados básicos

Teorema de Friedgut-Kalai-Naor

Si tiene grado como máximo 1, entonces es constante, igual a una coordenada o igual a la negación de una coordenada. En particular, es una dictadura : una función que depende como máximo de una coordenada. ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle f}$ ${\displaystyle f}$

El teorema de Friedgut–Kalai–Naor, ^[4] también conocido como teorema FKN , establece que si casi tiene grado 1, entonces está cerca de una dictadura. Cuantitativamente, si y , entonces está -cerca de una dictadura, es decir, para alguna dictadura booleana , o equivalentemente, para alguna dictadura booleana . ${\displaystyle f}$ ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle \|f^{>1}\|^{2}<\varepsilon }$ ${\displaystyle f}$ ${\displaystyle O(\varepsilon )}$ ${\displaystyle \|f-g\|^{2}=O(\varepsilon )}$ ${\displaystyle g}$ ${\displaystyle \Pr[f\neq g]=O(\varepsilon )}$ ${\displaystyle g}$

De manera similar, una función booleana de grado depende como máximo de coordenadas, lo que la convierte en una junta (una función que depende de un número constante de coordenadas), donde es una constante absoluta igual a al menos 1,5 y como máximo 4,41, como lo demuestra Wellens. ^[5] El teorema de Kindler-Safra ^[6] generaliza el teorema de Friedgut-Kalai-Naor a este contexto. Afirma que si satisface entonces es -cercano a una función booleana de grado como máximo . ${\displaystyle d}$ ${\displaystyle C_{W}2^{d}}$ ${\displaystyle C_{W}}$ ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle \|f^{>d}\|^{2}<\varepsilon }$ ${\displaystyle f}$ ${\displaystyle O(\varepsilon )}$ ${\displaystyle d}$

Teorema de Kahn-Kalai-Linial

La desigualdad de Poincaré para el cubo de Boole (que se desprende de las fórmulas que aparecen arriba) establece que para una función , ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

${\displaystyle \operatorname {Var} [f]\leq \operatorname {Inf} [f]\leq \deg f\cdot \operatorname {Var} [f].}$

Esto implica que . ${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\geq {\frac {\operatorname {Var} [f]}{n}}}$

El teorema de Kahn-Kalai-Linial, ^[7] también conocido como teorema KKL , establece que si es booleano entonces . ${\displaystyle f}$ ${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]=\Omega \left({\frac {\log n}{n}}\right)}$

El límite dado por el teorema de Kahn-Kalai-Linial es estricto y se logra mediante la función Tribes de Ben-Or y Linial: ^[8]

${\displaystyle (x_{1,1}\land \cdots \land x_{1,w})\lor \cdots \lor (x_{2^{w},1}\land \cdots \land x_{2^{w},w}).}$

El teorema de Kahn-Kalai-Linial fue uno de los primeros resultados en el área y fue el que introdujo la hipercontractividad en el contexto de las funciones booleanas.

Teorema de la junta de Friedgut

Si es una -junta (una función que depende como máximo de coordenadas) entonces según la desigualdad de Poincaré. ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \operatorname {Inf} [f]\leq M}$

El teorema de Friedgut ^[9] es un reverso de este resultado. Afirma que para cualquier , la función es -cercana a una junta booleana dependiendo de las coordenadas. ${\displaystyle \varepsilon >0}$ ${\displaystyle f}$ ${\displaystyle \varepsilon }$ ${\displaystyle \exp(\operatorname {Inf} [f]/\varepsilon )}$

Combinado con el lema de Russo-Margulis, el teorema de la junta de Friedgut implica que para cada , toda función monótona está cerca de una junta con respecto a para algún . ${\displaystyle p}$ ${\displaystyle \mu _{q}}$ ${\displaystyle q\approx p}$

Principio de invariancia

El principio de invariancia ^[10] generaliza el teorema de Berry-Esseen a funciones no lineales.

El teorema de Berry-Esseen establece (entre otras cosas) que si y no es demasiado grande en comparación con el resto, entonces la distribución de over es cercana a una distribución normal con la misma media y varianza. ${\displaystyle f=\sum _{i=1}^{n}c_{i}x_{i}}$ ${\displaystyle c_{i}}$ ${\displaystyle f}$ ${\displaystyle \{-1,1\}^{n}}$

El principio de invariancia (en un caso especial) establece informalmente que si es un polinomio multilineal de grado acotado sobre y todas las influencias de son pequeñas, entonces la distribución de bajo la medida uniforme sobre es cercana a su distribución en el espacio gaussiano. ${\displaystyle f}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \{-1,1\}^{n}}$

Más formalmente, sea una función Lipschitz univariante , sea , sea , y sea . Supongamos que . Entonces ${\displaystyle \psi }$ ${\displaystyle f=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}}$ ${\displaystyle k=\deg f}$ ${\displaystyle \varepsilon =\max _{i}\sum _{S\ni i}{\hat {f}}(S)^{2}}$ ${\displaystyle \sum _{S\neq \emptyset }{\hat {f}}(S)^{2}\leq 1}$

${\displaystyle \left|\operatorname {E} _{x\sim \{-1,1\}^{n}}[\psi (f(x))]-\operatorname {E} _{g\sim N(0,I)}[\psi (f(g))]\right|=O(k9^{k}\varepsilon ).}$

Al elegir apropiado , esto implica que las distribuciones de bajo ambas medidas están cerca en la distancia CDF , que está dada por . ${\displaystyle \psi }$ ${\displaystyle f}$ ${\displaystyle \sup _{t}|\Pr[f(x)<t]-\Pr[f(g)<t]|}$

El principio de invariancia fue el ingrediente clave en la prueba original del teorema de que la mayoría es la más estable.

Algunas aplicaciones

Prueba de linealidad

Una función booleana es lineal si satisface , donde . No es difícil demostrar que las funciones lineales booleanas son exactamente los caracteres . ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle f(xy)=f(x)f(y)}$ ${\displaystyle xy=(x_{1}y_{1},\ldots ,x_{n}y_{n})}$ ${\displaystyle \chi _{S}}$

En la prueba de propiedades queremos comprobar si una función dada es lineal. Es natural intentar la siguiente prueba: elegir uniformemente al azar y comprobar que . Si es lineal, entonces siempre pasa la prueba. Blum, Luby y Rubinfeld ^[11] demostraron que si la prueba pasa con probabilidad, entonces es -cerca de un carácter de Fourier. Su prueba fue combinatoria. ${\displaystyle x,y\in \{-1,1\}^{n}}$ ${\displaystyle f(xy)=f(x)f(y)}$ ${\displaystyle f}$ ${\displaystyle 1-\varepsilon }$ ${\displaystyle f}$ ${\displaystyle O(\varepsilon )}$

Bellare et al. ^[12] dieron una prueba analítica de Fourier extremadamente simple, que también muestra que si la prueba tiene éxito con una probabilidad , entonces está correlacionada con un carácter de Fourier. Su prueba se basa en la siguiente fórmula para la probabilidad de éxito de la prueba: ${\displaystyle 1/2+\varepsilon }$ ${\displaystyle f}$

${\displaystyle {\frac {1}{2}}+{\frac {1}{2}}\sum _{S\subseteq [n]}{\hat {f}}(S)^{3}.}$

Teorema de Arrow

El teorema de imposibilidad de Arrow establece que, para tres o más candidatos, la única regla de votación unánime para la cual siempre hay un ganador en el criterio de Condorcet es la dictadura.

La prueba habitual del teorema de Arrow es combinatoria. Kalai ^[13] dio una prueba alternativa de este resultado en el caso de tres candidatos utilizando el análisis de Fourier. Si es la regla que asigna un ganador entre dos candidatos dados sus órdenes relativos en los votos, entonces la probabilidad de que haya un ganador de Condorcet dado un voto uniformemente aleatorio es , de lo que se deduce fácilmente el teorema. ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle {\frac {3}{4}}-{\frac {3}{4}}\operatorname {Stab} _{-1/3}[f]}$

El teorema FKN implica que si es una regla para la cual casi siempre hay un ganador de Condorcet, entonces está cerca de una dictadura. ${\displaystyle f}$ ${\displaystyle f}$

Umbrales agudos

Un resultado clásico en la teoría de grafos aleatorios establece que la probabilidad de que un grafo aleatorio esté conectado tiende a si . Este es un ejemplo de un umbral agudo : el ancho de la "ventana de umbral", que es , es asintóticamente menor que el umbral mismo, que es aproximadamente . Por el contrario, la probabilidad de que un grafo contenga un triángulo tiende a cuando . Aquí tanto la ventana de umbral como el umbral mismo son , por lo que este es un umbral burdo . ${\displaystyle G(n,p)}$ ${\displaystyle e^{-e^{-c}}}$ ${\displaystyle p\sim {\frac {\log n+c}{n}}}$ ${\displaystyle O(1/n)}$ ${\displaystyle {\frac {\log n}{n}}}$ ${\displaystyle G(n,p)}$ ${\displaystyle e^{-c^{3}/6}}$ ${\displaystyle p\sim {\frac {c}{n}}}$ ${\displaystyle \Theta (1/n)}$

El teorema del umbral agudo de Friedgut ^[14] establece, en términos generales, que una propiedad de un grafo monótono (una propiedad de un grafo es una propiedad que no depende de los nombres de los vértices) tiene un umbral agudo a menos que esté correlacionada con la aparición de subgrafos pequeños. Este teorema se ha aplicado ampliamente para analizar grafos aleatorios y percolación .

En una nota relacionada, el teorema KKL implica que el ancho de la ventana de umbral es siempre como máximo . ^[15] ${\displaystyle O(1/\log n)}$

La mayoría es la más estable

Sea la función mayoritaria en coordenadas. La fórmula de Sheppard da la estabilidad asintótica del ruido de la mayoría: ${\displaystyle \operatorname {Maj} _{n}\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle n}$

${\displaystyle \operatorname {Stab} _{\rho }[\operatorname {Maj} _{n}]\longrightarrow 1-{\frac {2}{\pi }}\arccos \rho .}$

Esto está relacionado con la probabilidad de que si elegimos uniformemente al azar y formamos volteando cada bit de con probabilidad , entonces la mayoría permanece igual: ${\displaystyle x\in \{-1,1\}^{n}}$ ${\displaystyle y\in \{-1,1\}^{n}}$ ${\displaystyle x}$ ${\displaystyle {\frac {1-\rho }{2}}}$

${\displaystyle \operatorname {Stab} _{\rho }[\operatorname {Maj} _{n}]=2\Pr[\operatorname {Maj} _{n}(x)=\operatorname {Maj} _{n}(y)]-1}$.

Existen funciones booleanas con mayor estabilidad de ruido. Por ejemplo, una dictadura tiene estabilidad de ruido . ${\displaystyle x_{i}}$ ${\displaystyle \rho }$

El teorema de la mayoría es la más estable establece, informalmente, que las únicas funciones que tienen una estabilidad de ruido mayor que la mayoría tienen coordenadas influyentes. Formalmente, para cada existe tal que si tiene esperanza cero y , entonces . ${\displaystyle \varepsilon >0}$ ${\displaystyle \tau >0}$ ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\leq \tau }$ ${\displaystyle \operatorname {Stab} _{\rho }[f]\leq 1-{\frac {2}{\pi }}\arccos \rho +\varepsilon }$

La primera prueba de este teorema utilizó el principio de invariancia junto con un teorema isoperimétrico de Borell en el espacio gaussiano; desde entonces se idearon pruebas más directas. ^{[16] [17]}

La mayoría es más estable implica que el algoritmo de aproximación de Goemans-Williamson para MAX-CUT es óptimo, suponiendo la conjetura de juegos únicos . Esta implicación, debida a Khot et al., ^[18] fue el impulso detrás de la demostración del teorema.

Referencias

1. O'Donnell, Ryan (2014). Análisis de funciones booleanas . Cambridge University Press. arXiv : 2105.10386 . ISBN. 978-1-107-03832-5.
2. P. Diaconis ; L. Saloff-Coste (agosto de 1996). "Desigualdades logarítmicas de Sobolev para cadenas finitas de Markov". Anales de probabilidad aplicada . 6 (3): 695–750. doi : 10.1214/AOAP/1034968224 . ISSN  1050-5164. MR  1410112. Zbl  0867.60043. Wikidata  Q62111462.
3. Mossel, Elchanan; Oleszkiewicz, Krzysztof; Sen, Arnab (2013). "Sobre la hipercontractividad inversa". Análisis geométrico y funcional . 23 (3): 1062–1097. arXiv : 1108.1210 . doi : 10.1007/s00039-013-0229-4 . S2CID  15933352.
4. Friedgut, Ehud; Kalai, Gil; Naor, Assaf (2002). "Funciones booleanas cuya transformada de Fourier se concentra en los dos primeros niveles". Avances en Matemáticas Aplicadas . 29 (3): 427–437. doi : 10.1016/S0196-8858(02)00024-6 .
5. Wellens, Jake (2020). "Relaciones entre el número de entradas y otras medidas de complejidad de funciones booleanas". Discrete Analysis . arXiv : 2005.00566 . doi :10.19086/da.57741 (inactivo 2024-04-25).{{cite journal}}: CS1 maint: DOI inactive as of April 2024 (link)
6. Kindler, Guy (2002). "Capítulo 16" (PDF) . Pruebas de propiedad, PCP y juntas (Tesis). Universidad de Tel Aviv.
7. Kahn, Jeff; Kalai, Gil; Linial, Nati (1988). "La influencia de las variables en las funciones booleanas". Proc. 29.° Simposio sobre fundamentos de la informática . SFCS'88. White Plains: IEEE. págs. 68–80. doi :10.1109/SFCS.1988.21923.
8. Ben-Or, Michael; Linial, Nathan (1985). "Lanzamiento colectivo de monedas, esquemas de votación robustos y mínimos de valores de Banzhaf". Proc. 26.° Simposio sobre fundamentos de la ciencia informática . SFCS'85. Portland, Oregón: IEEE. págs. 408–416. doi :10.1109/SFCS.1985.15.
9. Friedgut, Ehud (1998). "Las funciones booleanas con baja sensibilidad promedio dependen de pocas coordenadas". Combinatorica . 18 (1): 474–483. CiteSeerX 10.1.1.7.5597 . doi : 10.1007/PL00009809 . S2CID  15534278. 
10. Mossel, Elchanan; O'Donnell, Ryan ; Oleszkiewicz, Krzysztof (2010). "Estabilidad de ruido de funciones con influencias bajas: invariancia y optimalidad". Anales de Matemáticas . 171 (1): 295–341. arXiv : math/0503503 . doi : 10.4007/annals.2010.171.295 .
11. Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt (1993). "Autoprueba/corrección con aplicaciones a problemas numéricos". J. Comput. Syst. Sci . 47 (3): 549–595. doi : 10.1016/0022-0000(93)90044-W .
12. Bellare, Mihir; Coppersmith, Don; Håstad, Johan; Kiwi, Marcos; Sudan, Madhu (1995). "Prueba de linealidad en característica dos". Actas del 36.º Simposio sobre fundamentos de la informática . FOCS'95.
13. Kalai, Gil (2002). "Una perspectiva teórica de Fourier sobre la paradoja de Condorcet y el teorema de Arrow" (PDF) . Avances en Matemáticas Aplicadas . 29 (3): 412–426. doi : 10.1016/S0196-8858(02)00023-4 .
14. Friedgut, Ehud (1999). "Umbrales agudos de propiedades de grafos y el problema k-SAT". Revista de la Sociedad Americana de Matemáticas . 12 (4): 1017–1054. doi : 10.1090/S0894-0347-99-00305-7 .
15. Friedgut, Ehud; Kalai, Gil (1996). "Cada propiedad de un grafo monótono tiene un umbral agudo". Actas de la American Mathematical Society . 124 (10): 2993–3002. doi : 10.1090/S0002-9939-96-03732-X .
16. De, Anindya; Mossel, Elchanan; Neeman, Joe (2016), "La mayoría es más estable: discreta y SoS" (PDF) , Theory of Computing , 12 (4): 1–50, CiteSeerX 10.1.1.757.3048 , doi :10.4086/toc.2016.v012a004 
17. Eldan, Ronen ; Mikulincer, Dan; Raghavendra, Prasad (junio de 2023). "Estabilidad del ruido en el hipercubo booleano a través de un movimiento browniano renormalizado". STOC 2023: Actas del 55.º Simposio anual de la ACM sobre teoría de la computación . STOC. Orlando, Florida: ACM. págs. 661–671. arXiv : 2208.06508 . doi :10.1145/3564246.3585118.
18. Khot, Subhash ; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "¿Resultados de inaproximabilidad óptimos para MAX-CUT y otros CSP de dos variables?" (PDF) , SIAM Journal on Computing , 37 (1): 319–357, CiteSeerX 10.1.1.130.8886 , doi :10.1137/S0097539705447372, S2CID  2090495