よく使う記法

• 自然数$n\in \mathbb{N}$に対して$[n]={1,\dots,n}$とする。
• 有限集合$S$に対し、$x\sim S$と書いたとき、要素$x$は$S$上一様ランダムに選ばれることを意味する。
  • 例えば$\Pr_{x\sim S}[\cdot]$と書くと、$S$上一様ランダムに選ばれた$x$に関する確率を考えることを意味する。
• より一般に、有限集合上の分布$\nu$に対し、$x\sim \nu$と書くと$x$は分布$\nu$に従って選ばれたことを意味する。
• 確率変数$X$に対して$\supp(X) = \{ x\colon \Pr[X=x]>0 \}$を$X$の台(サポート)という（基本的には$X$として離散的な値をとるもののみを考える）。
• アルゴリズム$\mathcal{A}$と入力$x$に対し、$\mathcal{A}(x)$はアルゴリズム$\mathcal{A}$の入力$x$に対する出力を表すことにする。
  • $\mathcal{A}$が乱択アルゴリズムの場合は$\mathcal{A}(x)$は確率変数として扱われる。
• グラフ$G=(V,E)$とは有限集合$V$と$E\subseteq\binom{V}{2}$のペアである。
  • 頂点$u\in V$の隣接点集合を$N(u)\subseteq V$で表す。