ブール関数の解析

数学および理論計算機科学において、ブール関数の解析とは、スペクトルの観点から、または（擬似ブール関数と呼ばれることもある）実数値関数を研究するものである。 ^[1]研究対象となる関数は、多くの場合ブール値を持つが、必ずしもそうではないため、ブール関数となる。この分野は、組合せ論、社会選択理論、ランダムグラフ、そして理論計算機科学、特に近似困難性、特性検定、PAC学習において多くの応用が見出されている。 ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle \{-1,1\}^{n}}$

基本概念

ここでは主に定義域 で定義された関数について考えます。定義域 を扱う方が便利な場合もあります。が で定義されている場合、 で定義された対応する関数は ${\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}}).}$

同様に、私たちにとってブール関数は- 値関数ですが、代わりに - 値関数を検討する方が便利な場合がよくあります。 ${\displaystyle \{-1,1\}}$ ${\displaystyle \{0,1\}}$

フーリエ展開

すべての実数値関数は、多重線型多項式として一意に展開されます。 ${\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}.}$

(関数の値が 0-1 であっても、これは 2 を法とする合計ではなく、単なる実数の通常の合計であることに注意してください。)

これは関数 のアダマール変換であり、群におけるフーリエ変換です。係数 はフーリエ係数と呼ばれ、全体の和はのフーリエ展開と呼ばれます。関数 はフーリエ指標と呼ばれ、 上のすべての関数の空間に対して、内積 に関して正規直交基底を形成します。 ${\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)}$

フーリエ係数は内積を使って計算できます。

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

特に、これは であることを示しています。ここで、期待値は上の一様分布に従って取られます。パーセバルの恒等式は、 ${\displaystyle {\hat {f}}(\emptyset )=\operatorname {E} [f]}$ ${\displaystyle \{-1,1\}^{n}}$

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

をスキップすると、 の分散は次のようになります。 ${\displaystyle S=\emptyset }$ ${\displaystyle f}$

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

フーリエ次数とフーリエレベル

関数の次数とは、大きさ の集合に対して となる最大値のことである。言い換えれば、 の次数は、その多重線型多項式としての次数である。 ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$ ${\displaystyle d}$ ${\displaystyle {\hat {f}}(S)\neq 0}$ ${\displaystyle S}$ ${\displaystyle d}$ ${\displaystyle f}$

フーリエ展開をレベルに分解すると便利です。フーリエ係数はレベルにあります。 ${\displaystyle {\hat {f}}(S)}$ ${\displaystyle |S|}$

の度数は ​${\displaystyle d}$ ${\displaystyle f}$

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

これは、レベル 以外のすべてのフーリエ係数をゼロにすることによって得られます。 ${\displaystyle f}$ ${\displaystyle d}$

同様に を定義します。 ${\displaystyle f^{>d},f^{<d},f^{\geq d},f^{\leq d}}$

影響

関数の ' 番目の影響は、次の 2 つの同等の方法で定義できます。 ${\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}}}$

がブール値の場合、 は、' 番目の座標を反転すると関数の値が反転する 確率です。${\displaystyle f}$ ${\displaystyle \operatorname {Inf} _{i}[f]}$ ${\displaystyle i}$

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

の場合は、 ' 番目の座標に依存しません。 ${\displaystyle \operatorname {Inf} _{i}[f]=0}$ ${\displaystyle f}$ ${\displaystyle i}$

の総影響度は、そのすべての影響度の合計です。 ${\displaystyle f}$

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

ブール関数の総影響度は、関数の平均感度でもあります。ある点におけるブール関数の感度とは、`番目の座標を反転すると関数の値が変化する座標の数です。この量の平均値が、まさに総影響度となります。 ${\displaystyle f}$ ${\displaystyle i}$ ${\displaystyle i}$

総影響は、適切に正規化された ハミンググラフの離散ラプラシアンを使用して定義することもできます。 ${\displaystyle \operatorname {Inf} [f]=\langle f,Lf\rangle }$

影響力の一般化された形式は、次のように定義される -安定影響力です。 ${\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}.}$

対応する総影響は

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

関数には最大で「一定数」の「安定的に影響力のある」座標が存在することが証明できる。 ${\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 }}.}$

ノイズ安定性

が与えられたとき、の周辺分布が一様で である場合、2つのランダムベクトルは-相関しているといいます。具体的には、最初に一様ランダムに選択し、次に各座標に独立して適用される次の2つの同等の規則のいずれかに従って選択することにより、 -相関ランダム変数のペアを生成できます。 ${\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}}}$

この分布を と表記します。 ${\displaystyle y\sim N_{\rho }(x)}$

関数のノイズ安定性は、次の2 つの同等の方法で定義できます。 ${\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}.}$

の場合、におけるのノイズ感度は ${\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].}$

がブール値の場合、これは各座標を の確率で独立して反転した場合にの値が変化する確率です。 ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \delta }$

ノイズ演算子

ノイズ演算子 は関数を受け取り、次の式で与えられる 別の関数を返す演算子です。${\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}.}$

のとき、ノイズ演算子は、各ビットが独立にレート1で反転する連続時間マルコフ連鎖を用いて定義することもできます。この演算子は、このマルコフ連鎖をから始まるステップで実行し、最終状態で の平均値を取ることに対応します。このマルコフ連鎖はハミンググラフのラプラシアンによって生成され、これはノイズ演算子への総影響を関連付けます。 ${\displaystyle \rho >0}$ ${\displaystyle T_{\rho }}$ ${\displaystyle {\frac {1}{2}}\log {\frac {1}{\rho }}}$ ${\displaystyle x}$ ${\displaystyle f}$

ノイズ安定性は、ノイズ演算子を使用して定義できます。 ${\displaystyle \operatorname {Stab} _{\rho }[f]=\langle f,T_{\rho }f\rangle }$

過収縮

の場合、関数の-ノルムは次のように定義されます。 ${\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}]}}.}$

また、次のように定義します${\displaystyle \|f\|_{\infty }=\max _{x\in \{-1,1\}^{n}}|f(x)|.}$

超収縮定理は、すべてのに対して 、${\displaystyle p>q>1}$ ${\displaystyle |\rho |\leq {\sqrt {\frac {q-1}{p-1}}}}$

${\displaystyle \|T_{\rho }f\|_{p}\leq \|f\|_{q}.}$

超収縮性は関数解析の対数ソボレフ不等式と密接に関連している。^[2]

同様の結果は逆超収縮性として知られている。^[3]これは、 ${\displaystyle 1>p>q}$ ${\displaystyle |\rho |\leq {\sqrt {\frac {1-p}{1-q}}}}$

${\displaystyle \|T_{\rho }f\|_{q}\geq \|f\|_{p}.}$

p-偏った分析

多くの場合、関数への入力は 上で一様分布するのではなく、またはへの偏りを持つ。このような状況では、関数を 上の領域で考えるのが通例である。 の場合、pバイアス測度は次のように与えられる。 ${\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})}.}$

この尺度は、各座標を独立して確率 で 1 、確率 で 0になるように選択することによって生成できます。 ${\displaystyle p}$ ${\displaystyle 1-p}$

古典的なフーリエ指標は、この測度に関してもはや直交しません。代わりに、以下の指標を使用します。

${\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\}|}.}$

の pバイアスフーリエ展開は、 pバイアス キャラクタ の線形結合としてのの展開です。${\displaystyle f}$ ${\displaystyle f}$

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

影響とノイズ演算子の定義は、スペクトル定義を使用してpバイアス設定に拡張できます。

影響

の影響は次のように表される。 ${\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}].}$

総影響度は個々の影響度の合計です。

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

ノイズ演算子

相関のある確率変数のペアは、独立に とを選択することで得られる。ここでは次のように与えられる。 ${\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}}}$

ノイズ演算子は次のように表される。

${\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)].}$

これを使用すると、以前と同様にノイズ安定性とノイズ感度を定義できます。

ルッソ・マルグリスの式

ルッソ・マルグリスの公式（マルグリス・ルッソの公式^[1]とも呼ばれる）は、単調なブール関数に対して、 ${\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}].}$

影響と確率はどちらも に関して取られ、右側の項には の平均感度が示されています。 を特性と考えると、式は が変化するにつれて、で発生する確率の導関数がでの平均感度に等しいことを示しています。 ${\displaystyle \mu _{p}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle p}$ ${\displaystyle f}$ ${\displaystyle p}$ ${\displaystyle p}$

ルッソ・マルギュリスの公式は、フリードガットのような鋭い閾値定理を証明するための鍵となります。

ガウス空間

この分野における最も深い成果の 1 つである不変性原理は、ブール キューブ上の関数の分布とガウス空間上の関数の分布を結び付けます。ガウス空間とは、標準的な次元ガウス測度を備えた空間です。 ${\displaystyle \{-1,1\}^{n}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle n}$

ブールキューブ上のフーリエ解析の基本概念の多くは、ガウス空間にも同等のものがあります。

• ガウス空間におけるフーリエ展開に対応するのはエルミート展開であり、これは多変数エルミート多項式の無限和（ に収束する）への展開である。${\displaystyle L^{2}}$
• セットの指標関数の総影響または平均感度に対応するのはガウス表面積であり、これはセットの境界のミンコフスキー内容です。
• ノイズ演算子に対応するのはオルンスタイン・ウーレンベック演算子（メーラー変換に関連）で、、または（は -相関標準ガウス分布のペア）で与えられます。${\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 }$
• 超収縮性は（適切なパラメータを使用すれば）ガウス空間でも成り立ちます。

ガウス空間はブールキューブよりも対称性が高く（例えば回転不変）、ブールキューブの離散的な設定では扱いにくい連続的な引数をサポートします。不変性原理はこれら2つの設定を結び付け、ガウス空間上の結果からブールキューブ上の結果を導き出すことを可能にします。

基本的な結果

フリードグート・カライ・ナオール定理

の次数が最大1である場合、 は定数、座標に等しい、または座標の否定に等しい。特に、は独裁関数、すなわち最大1つの座標に依存する関数である。 ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle f}$ ${\displaystyle f}$

フリードグート・カライ・ナオール定理^[4] （FKN定理としても知られる）は、がほぼ次数1であるとき、独裁制に近いことを述べています。定量的に言えば、およびの場合、独裁制に-近い、つまり、あるブール独裁制 に対して、あるいはそれと同値な、あるブール独裁制 に対して となります。 ${\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}$

同様に、最大次数のブール関数は最大で 個の座標に依存するため、定数個の座標に依存する関数（junta ）となる。ここで は、Wellens ^[5 ] によって示されているように、1.5以上4.41以下の絶対定数である。Kindler –Safraの定理^[6]は、Friedgut–Kalai–Naorの定理をこの設定に一般化したものであり、が を満たす場合、は最大で 次数のブール関数に -近いことを述べている。 ${\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}$

カーン・カライ・線形定理

ブール立方体のポアンカレ不等式（上記の式から導かれる）は、関数に対して、 ${\displaystyle f\colon \{-1,1\}^{n}\to \mathbb {R} }$

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

これは次のことを意味します。 ${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]\geq {\frac {\operatorname {Var} [f]}{n}}}$

カーン・カライ・リニアル定理^[7]はKKL定理としても知られ、がブール値のとき、となることを述べています。 ${\displaystyle f}$ ${\displaystyle \max _{i}\operatorname {Inf} _{i}[f]=\Omega \left({\frac {\log n}{n}}\right)}$

カーン・カライ・リニアル定理によって与えられた境界は厳密であり、ベン・オールとリニアルの部族関数によって達成される： ^[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}).}$

カーン・カライ・リニアル定理はこの分野における最初の結果の 1 つであり、ブール関数のコンテキストに超収縮性を導入したものです。

フリードグートの軍事定理

が-junta (最大で 座標に依存する関数)である場合、ポアンカレ不等式に従います。 ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle \operatorname {Inf} [f]\leq M}$

フリードグートの定理^[9]はこの結果の逆である。これは、任意の に対して、関数は座標に依存してブール関数に -近いことを述べている。 ${\displaystyle \varepsilon >0}$ ${\displaystyle f}$ ${\displaystyle \varepsilon }$ ${\displaystyle \exp(\operatorname {Inf} [f]/\varepsilon )}$

ルッソ・マルギュリスの補題と組み合わせると、フリードグートの軍事政権定理は、任意の に対して、任意の単調関数が、あるに対して に関して軍事政権に近いことを意味します。 ${\displaystyle p}$ ${\displaystyle \mu _{q}}$ ${\displaystyle q\approx p}$

不変性原理

不変性原理^[10]はベリー・エッシーンの定理を非線形関数に 一般化したものである。

ベリー・エッシーンの定理は、(他にも述べられているが)および が残りに比べて大きすぎる場合、 を超えるの分布は同じ平均と分散を持つ正規分布に近くなることを述べています。 ${\displaystyle f=\sum _{i=1}^{n}c_{i}x_{i}}$ ${\displaystyle c_{i}}$ ${\displaystyle f}$ ${\displaystyle \{-1,1\}^{n}}$

不変性原理（特殊な場合）は、が 上の有界次数の多重線型多項式であり、 のすべての影響が小さい場合、上の均一測度の下での の分布は、ガウス空間での分布に近いということを非公式に述べています。 ${\displaystyle f}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \{-1,1\}^{n}}$

より正式には、 を一変数リプシッツ関数とし、、、 とする 。 と仮定する。すると、 ${\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 ).}$

適切な を選択すると、両方の尺度における の分布がCDF 距離において近くなり、これは で与えられることを意味します。 ${\displaystyle \psi }$ ${\displaystyle f}$ ${\displaystyle \sup _{t}|\Pr[f(x)<t]-\Pr[f(g)<t]|}$

不変性原理は、多数決安定定理の最初の証明における重要な要素でした。

いくつかのアプリケーション

直線性テスト

ブール関数は、 （ただし ）を満たすとき線形関数である。ブール線形関数がまさに の指標であることを示すのは難しくない。 ${\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}}$

特性テストでは、与えられた関数が線形かどうかをテストします。次のようなテストを試みるのが自然です。一様ランダムに を選択し、 であることを確認します。が線形であれば、常にテストに合格します。Blum、Luby、およびRubinfeld ^[11]は、このテストが確率で合格する場合、 はフーリエ指標に -近いことを示し、その証明は組み合わせ論的でし た。${\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ら^​​[12]は極めて単純なフーリエ解析的証明を与え、この証明では、検定が確率 で成功するならば、 はフーリエ指標と相関していることも示しています。彼らの証明は、検定の成功確率を表す以下の式に基づいています。 ${\displaystyle 1/2+\varepsilon }$ ${\displaystyle f}$

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

アローの定理

アローの不可能性定理によれば、候補者が 3 人以上の場合、必ずコンドルセの勝者が出る唯一の全会一致の投票ルールは独裁制である。

アローの定理の通常の証明は組み合わせ論的である。カライ^[13]は、3人の候補者がいる場合のフーリエ解析を用いて、この結果の別の証明を示した。2人の候補者の相対的な投票順位を与えられた場合に、その中から勝者を決定する規則を とすると、一様ランダム投票においてコンドルセの勝者が存在する確率は となり、このことから定理は容易に導かれる。 ${\displaystyle f\colon \{-1,1\}^{n}\to \{-1,1\}}$ ${\displaystyle {\frac {3}{4}}-{\frac {3}{4}}\operatorname {Stab} _{-1/3}[f]}$

FKN 定理は、コンドルセ勝者がほぼ常に存在する規則である場合、独裁制に近いことを意味します。 ${\displaystyle f}$ ${\displaystyle f}$

鋭い閾値

ランダムグラフ理論における古典的な結論によれば、ランダムグラフが連結されている確率は の場合に に近づく傾向がある。これは鋭い閾値の例である。「閾値ウィンドウ」の幅は であり、閾値自体の幅（およそ ）よりも漸近的に小さくなる。対照的に、グラフに三角形が含まれる確率はの場合に に近づく傾向がある。ここでは閾値ウィンドウと閾値自体の両方が であるため、これは粗い閾値である。 ${\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)}$

フリードガットの鋭い閾値定理^{[14]は、大まかに言えば、単調なグラフ特性（グラフ特性とは、頂点の名前に依存しない特性）は、小さな部分グラフの出現と相関がない限り、鋭い閾値を持つことを示しています。この定理は、ランダムグラフや}パーコレーションの解析に広く応用されています。

関連する点として、KKL定理によれば閾値ウィンドウの幅は常に最大で となる。^[15]${\displaystyle O(1/\log n)}$

多数派が最も安定している

座標上の多数決関数を とします。シェパードの公式は、多数決関数の漸近的ノイズ安定性を与えます。 ${\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 .}$

これは、を一様にランダムに選択し、の各ビットを確率 で反転して を形成すると、大多数は同じままになる 確率と関係しています。${\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}$ 。

より大きなノイズ安定性を持つブール関数が存在します。例えば、独裁政権はノイズ安定性を持ちます。 ${\displaystyle x_{i}}$ ${\displaystyle \rho }$

多数決最安定定理は、非公式には、多数決よりも大きなノイズ安定性を持つ関数のみが影響力のある座標を持つと述べている。正式には、任意の に対して、が期待値ゼロかつ であるとき、となる関数が存在する。 ${\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 }$

この定理の最初の証明は、ガウス空間におけるボレルの等周定理と組み合わせて不変性原理を用いたが、その後、より直接的な証明が考案された。^{[16] [17]}

多数決が最も安定であることは、ユニークゲーム予想を仮定すると、 MAX-CUTに対するGoemans-Williamson近似アルゴリズムが最適であることを意味する。Khotら^[18]によるこの示唆は、定理を証明するきっかけとなった。

参考文献

1. オドネル、ライアン(2014).ブール関数の解析. ケンブリッジ大学出版局. arXiv : 2105.10386 . ISBN 978-1-107-03832-5。
2. P. ディアコニス; L. サロフ-コステ(1996 年 8 月)。 「有限マルコフ連鎖に対する対数ソボレフ不等式」。応用確率の年報。6 (3): 695–750。土井: 10.1214/AOAP/1034968224。ISSN  1050-5164。MR  1410112。Zbl 0867.60043  。ウィキデータ Q62111462。
3. Mossel, Elchanan; Oleszkiewicz, Krzysztof; Sen, Arnab (2013). 「逆超収縮性について」.幾何学と機能解析. 23 (3): 1062– 1097. arXiv : 1108.1210 . doi : 10.1007/s00039-013-0229-4 . S2CID  15933352.
4. Friedgut, Ehud; Kalai, Gil; Naor, Assaf (2002). 「フーリエ変換が最初の2つのレベルに集中しているブール関数」. Advances in Applied Mathematics . 29 (3): 427– 437. doi : 10.1016/S0196-8858(02)00024-6 .
5. Wellens, Jake (2020). 「ブール関数の入力数とその他の複雑性指標の関係」. Discrete Analysis . arXiv : 2005.00566 . doi :10.19086/da.57741 (2025年7月11日現在非アクティブ).
6. Kindler, Guy (2002). 「第16章」(PDF) .不動産鑑定、PCP、そして軍事政権(論文). テルアビブ大学.
7. Kahn, Jeff; Kalai, Gil; Linial, Nati (1988). 「ブール関数における変数の影響」. Proc. 29th Symp. on Foundations of Computer Science . SFCS'88. White Plains: IEEE. pp.  68– 80. doi :10.1109/SFCS.1988.21923.
8. ベン＝オール、マイケル；リニアル、ネイサン (1985). 「集団コイン投げ、堅牢な投票スキーム、そしてバンザフ値の最小値」. Proc. 26th Symp. on Foundations of Computer Science . SFCS'85. ポートランド、オレゴン州: IEEE. pp.  408– 416. doi :10.1109/SFCS.1985.15.
9. Friedgut, Ehud (1998). 「平均感度が低いブール関数は少数の座標に依存する」. 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). 「低影響関数のノイズ安定性：不変性と最適性」Annals of Mathematics . 171 (1): 295– 341. arXiv : math/0503503 . doi : 10.4007/annals.2010.171.295 .
11. Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt (1993). 「自己テスト／修正と数値問題への応用」J. Comput. Syst. Sci . 47 (3): 549– 595. doi : 10.1016/0022-0000(93)90044-W .
12. ベッラーレ、ミヒル;カッパースミス、ドン。ハスタッド、ヨハン。キウイ、マルコス。スーダン、マドゥ（1995）。 「特性 2 での直線性テスト」。手順36番目の症状。コンピュータサイエンスの基礎について。 FOCS'95。
13. Kalai, Gil (2002). 「コンドルセのパラドックスとアローの定理に関するフーリエ理論的視点」(PDF) .応用数学の進歩. 29 (3): 412– 426. doi : 10.1016/S0196-8858(02)00023-4 .
14. Friedgut, Ehud (1999). 「グラフ特性の鋭い閾値とk-SAT問題」.アメリカ数学会誌. 12 (4): 1017– 1054. doi : 10.1090/S0894-0347-99-00305-7 .
15. Friedgut, Ehud; Kalai, Gil (1996). 「すべての単調グラフ特性は鋭い閾値を持つ」アメリカ数学会紀要. 124 (10): 2993– 3002. doi : 10.1090/S0002-9939-96-03732-X .
16. De, Anindya; Mossel, Elchanan; Neeman, Joe (2016)、「多数決は安定する：離散とSoS」（PDF）、コンピューティング理論、12（4）：1– 50、CiteSeerX 10.1.1.757.3048、doi：10.4086/toc.2016.v012a004  
17. Eldan, Ronen ; Mikulincer, Dan ; Raghavendra, Prasad (2023年6月). 「ブール超立方体における再正規化ブラウン運動によるノイズ安定性」. STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing . STOC. Orlando, Florida: ACM. pp.  661– 671. arXiv : 2208.06508 . doi :10.1145/3564246.3585118.
18. Khot, Subhash ; Kindler, Guy ; Mossel, Elchanan ; O'Donnell, Ryan (2007) 「MAX-CUTとその他の2変数CSPの最適近似不可能性結果？」(PDF)、SIAM Journal on Computing、37 (1): 319– 357、CiteSeerX 10.1.1.130.8886、doi :10.1137/S0097539705447372、S2CID  2090495