Análisis de funciones booleanas.

Estudio de funciones booleanas mediante análisis discreto de Fourier.

En matemáticas e informática teórica , el análisis de funciones booleanas es el estudio de funciones con valores reales en o (dichas funciones a veces se conocen como funciones pseudobooleanas ) desde una perspectiva espectral. ^[1] Las funciones estudiadas suelen tener, aunque no siempre, valores booleanos, lo que las convierte en funciones booleanas . El área ha encontrado muchas aplicaciones en combinatoria , teoría de la elección social , gráficos aleatorios e informática teórica, especialmente en dureza de aproximación , pruebas de propiedades y aprendizaje PAC . ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle \{-1,1\}^{n}}$

Conceptos básicos

Principalmente consideraremos funciones definidas en el dominio . A veces es más conveniente trabajar con el dominio . Si está definido 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 valores, aunque a menudo es más conveniente considerar funciones con valores. ${\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-1, esta no es una suma mod 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 completa se conoce como expansión de Fourier . Las funciones se conocen como caracteres de Fourier y forman una base ortonormal para el espacio de todas las funciones 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 mediante un producto interno:

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

En particular, esto muestra 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 , obtenemos la varianza de : ${\displaystyle S=\emptyset }$ ${\displaystyle f}$

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

Grado de Fourier y niveles de Fourier

El grado de una función es el máximo tal que para algún 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 niveles . ${\displaystyle {\hat {f}}(S)}$ ${\displaystyle |S|}$

La parte de grado ${\displaystyle d}$ de 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}$

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

Influencia

La 'ésima influencia de una función se puede definir de dos formas 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 'ésima coordenada 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 'ésima coordenada. ${\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 promedio 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 uniformemente al azar y luego eligiendo de acuerdo con una de las dos reglas equivalentes siguientes, aplicadas de forma independiente 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 al ruido de una función en 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 , de forma independiente. ${\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 usando una cadena de Markov de tiempo continuo en la que cada bit se invierte de forma independiente con velocidad 1. El operador corresponde a ejecutar esta cadena de Markov para pasos que comienzan en y tomando el valor promedio de en el estado final. . Esta cadena de Markov es generada por el laplaciano del gráfico de Hamming, y este 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 la hipercontractividad establece que para cualquiera 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}$

p -Análisis sesgado

En muchas situaciones, la entrada a la función no se distribuye uniformemente , sino que tiene un sesgo hacia o . En estas situaciones se acostumbra considerar funciones sobre el dominio . Para , la medida p -sesgada 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 de forma independiente para que sea 1 con probabilidad y 0 con probabilidad . ${\displaystyle p}$ ${\displaystyle 1-p}$

Los caracteres clásicos de Fourier ya no son ortogonales con respecto a 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 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 el operador de ruido al entorno con polarización p 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 está 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 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 media de . Si pensamos en 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 umbrales definidos 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 booleano 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 booleano tienen contrapartes 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 hasta una suma infinita (convergiendo en ) de polinomios de Hermite multivariados . ${\displaystyle L^{2}}$
• La contraparte de la influencia total o sensibilidad promedio para 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 gaussianos estándar correlacionados. ${\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 mantiene (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 de rotación) y admite argumentos continuos que pueden ser más difíciles de entender en el entorno discreto del cubo booleano. El principio de invariancia vincula las dos configuraciones y permite deducir resultados en el cubo booleano a partir de 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, se trata de 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 de 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 de manera equivalente, 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 como máximo coordenadas, lo que la convierte en una junta (una función que depende de un número constante de coordenadas), donde una constante absoluta es igual a al menos 1,5 y como máximo a 4,41, como se muestra en Wellens. ^[5] El teorema de Kindler-Safra ^[6] generaliza el teorema de Friedgut-Kalai-Naor a este escenario. Afirma que si satisface entonces está cerca de 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 booleano (que se deriva 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 de 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 estrecho 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 las 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 opuesto a este resultado. Afirma que para any , la función está cerca de 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 , cada función monótona está cerca de una junta con respecto a para algunos . ${\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 está cerca de 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 y todas las influencias de son pequeñas, entonces la distribución de bajo la medida uniforme 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 de Lipschitz univariada , let , let y let . Suponer 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 cercanas en distancia CDF , que viene 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 demostración original del teorema de la mayoría es 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 las pruebas de propiedades queremos probar 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 está 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 probabilidad , entonces se correlaciona 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 flecha

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

La demostración habitual del teorema de Arrow es combinatoria. Kalai ^[13] proporcionó 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 dado su orden relativo en los votos, entonces la probabilidad de que haya un ganador de Condorcet dado un voto uniformemente aleatorio es , de lo cual se sigue 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 de FKN implica que si es una regla en la que 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 definido : el ancho de la "ventana de umbral", que es , es asintóticamente más pequeño que el umbral mismo, que es aproximadamente . Por el contrario, la probabilidad de que una gráfica contenga un triángulo tiende a cuando . Aquí están tanto la ventana de umbral como el umbral mismo , por lo que se trata de un umbral aproximado . ${\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 gráfico monótono (una propiedad de gráfico es una propiedad que no depende de los nombres de los vértices) tiene un umbral agudo a menos que esté correlacionado con la aparición de subgrafos pequeños. . Este teorema se ha aplicado ampliamente para analizar gráficos aleatorios y percolación .

En una nota relacionada, el teorema de 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 más estable

Denotemos la función mayoritaria en coordenadas. La fórmula de Sheppard da la estabilidad del ruido asintótico 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 invirtiendo cada bit 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 del ruido. Por ejemplo, una dictadura tiene estabilidad acústica . ${\displaystyle x_{i}}$ ${\displaystyle \rho }$

El teorema de la mayoría es más estable establece, de manera informal, que las únicas funciones que tienen una estabilidad de ruido mayor que la mayoría tienen coordenadas influyentes. Formalmente, para cada existe algo tal que si tiene expectativa 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, asumiendo la conjetura de los 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 . Prensa de la Universidad de Cambridge. 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. SEÑOR  1410112. Zbl  0867.60043. Wikidata  Q62111462.
3. Mossel, Eljanán; 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, Aod; Kalai, Gil; Naor, Assaf (2002). "Funciones booleanas cuya transformada de Fourier se concentra en los dos primeros niveles". Avances en Matemática Aplicada . 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". Análisis discreto . 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, chico (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. Llanuras blancas: 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 sólidos y valores mínimos de Banzhaf". Proc. 26º Simposio. sobre Fundamentos de la 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 sensibilidad media baja dependen de pocas coordenadas". Combinatoria . 18 (1): 474–483. CiteSeerX 10.1.1.7.5597 . doi : 10.1007/PL00009809 . S2CID  15534278. 
10. Mossel, Eljanán; O'Donnell, Ryan ; Oleszkiewicz, Krzysztof (2010). "Estabilidad del ruido de funciones con bajas influencias: Invariancia y optimización". Anales de Matemáticas . 171 (1): 295–341. arXiv : matemáticas/0503503 . doi : 10.4007/anales.2010.171.295 .
11. Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt (1993). "Autocomprobación/corrección con aplicaciones a problemas numéricos". J. Computación. Sistema. Ciencia . 47 (3): 549–595. doi : 10.1016/0022-0000(93)90044-W .
12. Bellare, Mihir; Calderero, Don; Hastad, Johan; Kiwi, Marcos; Sudán, Madhu (1995). "Prueba de linealidad en la característica dos". Proc. 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ática Aplicada . 29 (3): 412–426. doi : 10.1016/S0196-8858(02)00023-4 .
14. Friedgut, Ehud (1999). "Umbrales agudos de las propiedades del gráfico y el problema k-SAT". Revista de la Sociedad Matemática Estadounidense . 12 (4): 1017-1054. doi : 10.1090/S0894-0347-99-00305-7 .
15. Friedgut, Aod; Kalai, Gil (1996). "Cada propiedad de gráfico monótono tiene un umbral agudo". Actas de la Sociedad Matemática Estadounidense . 124 (10): 2993–3002. doi : 10.1090/S0002-9939-96-03732-X .
16. De, Anindya; Mossel, Eljanán; Neeman, Joe (2016), "La mayoría es más estable: discreta y SoS" (PDF) , Teoría de la Computación , 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 mediante un movimiento browniano renormalizado". STOC 2023: Actas del 55º Simposio Anual 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, chico; Mossel, Eljanán; O'Donnell, Ryan (2007), "¿Resultados óptimos de inaproximabilidad para MAX-CUT y otros CSP de dos variables?" (PDF) , Revista SIAM de Computación , 37 (1): 319–357, CiteSeerX 10.1.1.130.8886 , doi :10.1137/S0097539705447372, S2CID  2090495