数理解析研究所講究録
第 1849 巻 2013 年 109-115
2012 年度冬の LA シンポジウム [S16]109

A Fourier analytic approach to list-decoding
for sparse random linear codes
山根一航*

河内亮周 *

平成 25 年 3 月 15 日

概要考えられる元のメッセージの候補をもれなく列挙する問題である．リスト復号の問題は，元のメッセー

疎なランダム線形符号のリスト復号問題はこれま ジを一意に推測しなければならない一意復号の問題
で時間効率的なアルゴリズムが知られていない重要 とは異なり，高いエラー率にも対処することができ，な問題である．Kopparty と Saraf はこの問題に対し 広い応用を持つ．例えば疑似乱数の理論では疑似乱て受信語へのクエリー回数が効率的なリスト復号器 数生成器などの疑似乱数性証明にリスト復号器を用を構成した [3]. 彼らの手法は疎なランダム線形符号のリスト復号問題を時間効率的なリスト復号が可能な Hadamard 符号のリスト復号問題への帰着を与えいたり [1], 学習理論でも与えられた学習対象のサン

プルに誤りが付与された場合の学習アルゴリズム [6]に応用できることが知られている．このように理論るというものである．本論文では Kopparty と araf 計算機科学の多くの分野で考えられる問題は単純なと同様にクエリー回数が効率的な疎なランダム線形 リスト復号の問題として統一的に解釈でき，広い応$S$

符号の別のリスト復号器を構成する．Kopparty とSaraf が組合せ論的な操作により他の符号への帰着を与えたのに対して我々のアルゴリズムは Fourier 解用を持つ．より詳しくはリスト復号およびその応用に関するサーベイ論文 [5] を参照せよ．
そのようなリスト復号問題について，本論文では析的な手法を用いることでより直接的なリスト復号 特にランダム線形符号を議論する．ランダム線形符器となっている．

1

はじめに誤り訂正符号は計算機科学の中でも重要な研究対象であり，とりわけリスト復号と呼ばれる復号の問
題は，理論計算機科学における他の問題との深い関連性を持つことが知られている．リスト復号とは，任意のメッセージを，固定された符号で符号化して得た符号語が，ノイズの付与する通信路を通して送られてきたという設定の下で，通信路のエラー率の上界と送られてきた受信語をもらって，その情報から

号とは，生成行列をランダムに選ぶような線形符号のことである．ランダム線形符号の復号は歴史が長く，本質的に難しい問題であると思われてきた．しかし 2007 年に Kaufman と Sudan は，低エラー率の場合に限り，符号語数が符号語長の多項式で抑えられる疎なランダム線形符号に対してクエリー効率
的に一意復号が可能であることを示した [2]. ここ
でクエりー効率的とは，復号器が受信語 の全ビッ
トを読むのではなく， のビットごとのアクセスが可能なモデルにおいて，読み取るのビット数がで抑えられる場合 (つまり受信語 が
poly
$w$

$w$

$w$

$(n, 1/\epsilon)$

オラクル$i\mapsto w_{i}$$w$として与えられた場合にこのオラク

l へのクエリー回数が poly $(n, 1/\epsilon))$ をいう．さらに$\triangleright$’Dept. Math. & Comp. Sci., Tokyo Instute of Technology

2010 年には Kopparty と araf が，疎なランダム線
$S$

110
形符号のリスト復号を Hadamard 符号のリスト復号
へ帰着することによって，高エラー率の下での，クエリー効率的リスト復号器を与えた [3]. Hadamard 符号のリスト復号は，いくつかのアルゴリズムによって効率的に解くことが出来ることが知られている [1,4].
ここで効率的という場合にはクエリー効率的かつ復号器の時間計算量も poly$(n, 1/\epsilon)$で抑えられる場合をいう．
このように Kopparty と araf のアプローチはラン$S$(リスト) 復号問題

2.1

本論文では誤り訂正符号の復号問題を考える． 通$\circ$

信路のモデルとしては予め決まった数の任意のビットが反転するエラーを与えるものを考える．つまり
符号語 $c(x)$ とその受信語 $w$ に対してエラーベクト
ノレ $e:=w-c(x)$ が優位度パラメータ $\epsilon\in(0,1)$ で表される条件 wt $(e)\leq(1-\epsilon)/2$ を満たすことだけが保証される．ここで wt $(e)$ を$w$のエラー率と呼ぶ．符

号 $C=\{c(x)\in F_{2}^{N}|x\in’F_{2}^{n}\}$ の復号問題はさまざダム線形符号に対するリスト復号器を設計したとい
まな定式化が考えられるが，本論文で対象とするのうよりもランダム線形符号と Hadamard 符号の関連
は，通信路のエラー率の上界と送られてきた受信語
性を組合せ論的な方法から明らかにした結果であり，直接的にランダム線形符号のリスト復号器を設計したものではない．本論文では Kushilevitz と Mansourの，Fourier 解析的性質を利用した学習アルゴリズム[4](以下$KM$ アルゴリズムと呼ぶ)に着目し，それを拡張することによって疎なランダム線形符号に対するクエリー効率的リスト復号器を直接的に構成した．この拡張 $KM$ アルゴリズムは Kopparty と Sarafのものと同様時間効率的ではないが，よりアルゴリ
ズム的なアプローチであり，時間効率的なランダム線形符号のリスト復号器に向けての新たな知見を与え，またそのような Fourier 解析的手法が疎なラン-

ダム線形符号に対しても有用であることを示すものから考えうるメッセージ候補をもれなく列挙するリスト復号の問題である．
問題 2.1 ( $C$ のリスト復号).

任意の受信語 $w\in F_{2}^{n}$ と優位度パラメータ$(0,1)$$\epsilon\in$を受け取って，$\{x\in F_{2}^{n}|\Delta(c(x), w)\leq(1-$$\epsilon)/2\}\subseteq L$

を満たす$L\subseteq$

理を求めよ．

本論文を始め，多くの論文ではリスト復号器の性能を次の 2 つの観点から評価を行っている．1 つ目はクエリー数であり，2 つ目はリストサイズである．
リストサイズはそのまま出力リスト$L$の要素数 $|L|$のことを指すが，クエリー数については以下に説明
する．

である．

標準的な誤り訂正符号の理論では受信者は受信語の全ビットを読むことを前提に復号を行う場合が多

2

準備

$n$

本論文ではアルファベットとして二元体 F2$:=$のみを対象とする．長さ $k\in N$ の語または文字列 とは，各成分が F2 の元であるような 次$k\geq 1$ のときはの $i\in[k]$元の行ベクトルである．
文字目をと書く．つまり $w:=(w_{1}, \ldots, w_{k})$ であ$\{0,1\}$

$k$

$w$

$w$

$w_{i}$る．また$w$の長さを $|w|$ で表し，文字列 $v,$ $w$ の連結

を $vw$ で表す． のみからなる長さ
$0$

$k$

の文字列を

$0^{k}$と書き，文脈で長さが判断できる場合は単に 0 と書
$w$ の正規化ハミング重みを wt $(w):=|\{i\in[k]|$く．
$w_{i}\neq 0\}|/|w|$

いが，理論計算機科学の文脈ではメッセージ長 に対して非常に長い符号語 $N$ に対する復号を考えることが多い．このような場合，復号器は符号語に対して局所的なアクセスを行うことで復号を行う．つまで定義し， と$v$

$w$の正規化ハミング距

離を $\Delta(v, w)$ $:=$ wt $(v-w)$ で定義する．

を関数 (オラクル)
:
り，受信語
に対して
$i\in[N]$としてみな、し，復号器はクエリー$w\in F_{2}^{N}$$w_{i}\in F_{2}$$w$$\’{i}\prime N]arrow F_{2}$をオラクル $w:i\mapsto w_{i}$ から受け取ることができる．復号のために必要なこのクエリー数を性能評価に用いる．

我々の目標はこの 2 つの量を $n,$

$1/\epsilon$の多項式で抑えることである．これを達成するリスト復号器をク

エリー効率的なリスト復号器と呼ぶことにする．

111
2.2

ランダム線形符号$f(x)= \sum_{a\in F_{2}}\langle f,$ $\chi_{a}\rangle\chi_{a}(x)$$\ell_{2}$ノルムを$\Vert f\Vert_{2}$$\langle f,$$f\rangle$が成り立つ．また， の$f$の平方根で定義すると，次本論文を通してランダム線形符号と呼ばれる符号がの等式が成り立つことが知られている．
議論の中心となる．ランダム線形符号は，各要素を独立に 1/2 の確率で か 1 に決めて作られたランダム行 命題 2.3 (Parseval の等式).
$0$$\Vert f\Vert_{2}=\sum_{a\in F_{2}}\langle f,$列を生成行列とする線形符号である．

$2^{n}\leq$poly $(N)$$\chi_{a}\rangle^{2}.$

本論文では，内積の拡張にあたる 半内積と，合となるような大きな符号語長をもつランダム線形符$\mu$

成積の拡張にあたる$\mu$

合成積を用いる．

号を疎なランダム線形符号という．
符号 の偏りは bias $(C)$ $:= \max_{c\in C-\{0\}}|1/2-$ 定義 2.4 (上の半内積， 合成積). を
wt $(c)|$ で定義され，ある定数 $\gamma>0$ が存在して， 分布とする．
に対して半内
bias $(C)\leq N^{-\gamma}$ を満たすとき， は不偏であると 積を $E_{Y\sim\mu}[f(Y)g(Y)]$ で定義する．また，$Y^{(l)}\sim\mu$$Y^{(1)}+\cdots+Y^{(l)}$ が従ういう．ランダム線形符号の偏りについて次の定理がとし，成り立つ．(この定理は簡単であるため証明は省略 分布をと書くとき， の 階 合成積
$C$

$\mu$

$\mu$

$f$

$C$

$\langle f,$$\in$$\mathcal{F}_{n},$$F_{2}^{n}$

$\mu$

$l$

$\in$

$N$

$\mu$

$g\rangle_{\mu}$$Y^{(1)},$$\ldots,$$\mu^{(l)}$する．)

を $\mu^{(l)}(y)$$0$る以上の確率で bias $(C)\leq\beta.$$y\in F_{2}^{n}$

ついてFourier 解析

本論文では問題の定式化や証明に Fourier 解析の道具を用いる．ここでは Fourier 解析についての基 2.4
本的な定義や事実について簡単にまとめる．関数の空間として $F_{n}:=\{f:F_{2}^{n}arrow \mathbb{R}\}$ を考える．これは上の$\langle f^{[\mu,t]},$$f\in \mathcal{F}_{n},$

$y$

$n$

$2^{n}$$\vdash$$a\in F_{2}^{n}$$\chi_{a}\rangle_{\mu^{(l)}}=\langle f,$

で$f^{[\mu,l]}(y)$$:=$$\mu^{(l)}(y)=0$となと$F_{2}^{n}$上の分布に$\chi_{a}\rangle_{\mu}^{l}.$$KM$ アルゴリズム$KM$ アルゴリズム$|$

次元ベクトル空間とみなすことができる．任意のに対して次のように内積を，$\mathbb{R}$$\mu$$F_{2}^{n}$

では $f^{[\mu,l]}(y)$ $:=0$ と定義する．

命題 2.5. 任意の

2.3

となる

$f^{[\mu,l]}$

$l$

$\in$

$E[\prod_{i=1}^{l}f(Y^{(i)})|\sum_{i=1}^{l}Y^{(i)}=y],$定理 2.2. 任意の $\beta\in(0,1),$ $n,$ $N\in N$ に対して，$1-O(2^{n}\exp\{-\beta^{2}N/6\})$

$f$

$>$

[4] は関数の学習などに用いらるが，正確には次で定義される Fourier 基底ベク
/ 列挙問題を効率的に解くアルゴリズムである．
$\triangleright$$f,$ $g\in \mathcal{F}_{n}$$\langle f,$は$g\rangle:=E_{X\sim U_{n}}[f(X)g(X)j$$F_{2}^{n}$

字列

$a$

上の一様分布である．また，長さでラベル付けられた関数定義する． こで$(-1)^{a\cdot x}T\backslash \grave{}$$\langle_{-}arrow$である．

$f\in \mathcal{F}_{j,g}\in F_{k}$$f\cdot g$と定義する．ここで$k\in N$ の文を$\chi_{ab}=\chi_{a}\cdot\chi_{b}$$(x)$ $:=$

$g,$を満たすリスト$\{a\in F_{2}^{n}|\in\leq|\langle f, \chi_{a}\rangle|\}\subseteq L$

-

に対し，

$f\cdot g\in \mathcal{F}_{j+k}$を$\lrcorner$, および $|a|=|b|$ のは $x=0^{k}$ な

らば $\delta_{k}(x)=1$ それ以外は $\delta_{k}(x)=0$ となる関数

を求めよ．

アルゴリズムを簡単に説明をするために次のうな完全 2 分木を考える．各節点はの元であ, 根は空列である．節点
は節点
と節
$KM$

$\epsilon k$$e$が成り立つことなどは簡$\delta_{k}\in \mathcal{F}_{k}$$L\subseteq F_{2}^{n}$$a,$ $b\in F_{2}^{*}$$\sum_{v\in F_{2}^{k}}\chi_{v}(a)=$単に確かめられる．ここでしきい値 $\epsilon\in(0,1)$ が入力として与えられたと$a\cdot x=a_{1^{X}1}+\cdots+a_{k^{X}k}$

であること，$\chi_{b}\rangle=\delta_{k}(a+b)$,。

$\backslash$$2^{k}E_{X\sim U_{k}}[\chi_{a}(X)]=2^{k}\delta_{k}(a)$$\langle\chi_{a},$$T$$\chi$

題 2.6 (Fourier 基底ベクトル列挙問題通常版).

数 $f$ : $F_{2}^{n}arrow[-1, +1]$ がオラクル $x\mapsto f(x)$ とし$\ovalbox{\tt\small
REJECT}$$|$: $xy\mapsto f(x)g(y)$ で定義する．任意の

について

とき

$\chi_{a}\in \mathcal{F}_{k}$$FE$$U_{n}$$|$$\mathfrak{h}$$F_{2}^{\leq n}$$\alpha\in F_{2}^{<n}$$\alpha 0$を子に持つ．そして葉として の元 つまり
X ッセージが並ぶ．
を満たすを必$f_{|5_{\backslash }\alpha 1}$$f_{1}$$F_{2}^{n}$$\epsilon\leq\langle f,$$\cong$$\exists$な葉と呼ぶ．

$KM$$\chi_{a}\rangle$$a\in F_{2}^{n}$

アルゴリズムはこの木の節点をである．{ a}a ,、は端の正規直交基底となるが．
7\S から順に深さ優先的に訪問する．その際 訪問しこれを Fourier 基底と呼び，Fourier 基底の各要素
節点が 必要な葉を子孫として持ち得るかどうかを Fourier 基底ベクトルと呼ぶ．基底の性質から，後述する方法により評価し，持ち得ないことがわ$\chi$$\in$$7_{1}$$f$$f_{\overline{\llcorner}}$$P,$$\epsilon$

112
かるとその頂点を根とする部分木を枝刈りする．最 3.1 Fourier 基底ベクトル列挙問題への帰後まで枝刈りされることなく残った葉の中には，必着要な葉がすべて含まれていることになる．
本節では線形符号のリスト復号の問題が Fourierに対して枝刈りの基準を定めるために，を定義す 基底ベクトル列挙問題に帰着出来ることを示す．た見積もり関数
基底ベクトル列挙の問題
ならば節点 は必要な葉を子孫とし だしそのためには Fourier
る．
を問題
2.6
よりも一般的な形にしておく必要がある．
て持たないので， を根とする部分木は枝刈りする$\alpha\in F_{2}^{k}$$S_{2}(\alpha)$$\chi_{a}\rangle^{2}$$:= \sum_{\alpha’\in F_{2}^{\mathfrak{n}-k}}\langle f,$$S_{2}(\alpha)<\epsilon^{2}$$\alpha$$\alpha$

ことができる．この枝刈りの操作は，訪問する節点
数を poly$(n, 1/\epsilon)$

個に抑え，また，必要でない葉を$\mu$

を理上の分布とする．定義 2.4 で定義した

$\mu$

半内

積を用いて問題 2.6 を一般化した次の問題を考える．

ふるい落として出力リストサイズを絞る効果がある． 問題 3.2 (Fourier 基底ベクトル列挙問題拡張版).
は定義どおり判定すると多くの時間を必要とするが，Fourier 基底の
枝刈り条件

内積

$\langle\cdot,$$\cdot\rangle$$S_{2}(\alpha)$$<$$\epsilon^{2}$における直交性を利用すると，$S_{2}(\alpha)$

$+$

.

ここで

$X^{(1)},$ $X^{(2)}$$X^{(1)_{>k}}+X^{(2)_{>k}}$$iid\sim$$U_{n}$$=$$0]$$\epsilon\in(0,1)$が入力として与えられたときに，ト$L\subseteq$

を満たすリス

理を求めよ．

$=$$E_{X(1)X\sim U_{n}}(2)^{I.l.d}[f(X^{(1)})f(X^{(2)})\chi_{\alpha}(X^{(1)_{\leq k}}$$X^{(2)_{\leq k}})$て，しきい値$\{a\in F_{2}^{n}|\epsilon\leq|\langle f, \chi_{a}\rangle_{\mu}|\}\subseteq L$は次のような期待値の形に変形でき，サンプ
ル平均により効率的に近似できる:$S_{2}(\alpha)$

関数 $f$ : $F_{2}^{n}arrow[-1,1]$ がオラクル $x\mapsto f(x)$ としである．これにより一回の枝刈り判定も効率的に行え，全体としても効率的に任意の線形符号 $C$ に対して，問題 2.1 は問題 3.2に帰着出来ることが知られている．それを示すためにいくつか記号を準備する．線形符号 $C$ の生成行列$V:=\{g_{1^{T}}, \ldots, g_{N^{T}}\}$ とを $G=(g_{1}, \ldots, g_{N})$ とし，する．簡単のため動作する．

$g_{1},$$\ldots,$$g_{N}$

はすべて異なるベクト

ルであるとする．ランダム線形符号は高い確率でこ3

Fourier 解析的アプローチによん $(x)=(-1)^{w}$ : それ以外は $\delta_{k}(x)=0$ として定義す

本節の目標は次の定理を示すことである．

定理 3.1(疎なランダム線形符号のクエリー効率的なリスト復号). 疎なランダム線形符号 $C$ を選んだ
$C$ に対して問とき確率 1 $o(1)$ で以下が成り立つ．
, クエリー数
トサイズ poly$O(n\ln(n/\epsilon))$$(1/\epsilon)$$\epsilon^{-O(1)}.$で定数確率以上で解ける．

ここで $1/\epsilon=2^{\Omega(n)}$$w$$f_{w}$

るリスト復号

題 2.1 はリス-の仮定を満たすこと，この後の議論は一般の場合に容易に拡張可能であることを補足する．受信語 に$x=g_{j}^{T}$ ならば対して関数: $F_{2}^{n}arrow[-1,1]$ を，

る．また

$C$

に関連した分布となる自明なアルゴリ
ズムによって問題を解くことが出来るため，以下では $1/\epsilon=2^{o(n)}$ となる場合のみを考える．
$2^{n}$

定理 3.1 を示すために 3.1 節でまず問題 2.1 を後述

を $V$ の上での一様分布として定義する．次の補題が成り立つ．
補題 3.3. 問題 2.1 は問題 3.2 に帰着可能であり，後者がリストサイズ $|L|$ , クエリー数 $Q$ で解けるならば前者はリストサイズ $O(|L|)$ , クエリー数 $O(Q)$ で解ける．

となる極端な状況では，リス 証明．受信語

トサイズやクエリー数が$\mu$$w\in F_{2}^{N}$と優位度パラメータ$\epsilon\in(0,.1)$についての問題 2.1 を解きたいとしよう．関数んへのオラクル $x\mapsto f_{w}(x)$ は へのオ
ラクノ iw で模倣することができ，この計算にに対して符号$C$$w$$\triangleright$$\mapsto$$\ovalbox{\tt\small REJECT}$$C$ に関連おける $w$ へのクエリー数は $O(1)$ である．

をとり，関数んとしきい値 に対しての問題 3.2 に帰着し，その問題 3.2 を解くための拡張$KM$ アルゴリズムを 3.2 節で構成する．また 3.3 節についての問題 3.2 を解いて得られた解をでそのアルゴリズムの解析を行う．

と，定義からわかるように，した分布$\epsilon$

$\mu$

$L$

$\mu$

とする

$\Delta(w, c(a))\leq(1-\epsilon)/2$113
はと同値であり，これらが成り立つ ] gorithm EKMが成り立つ．すなわち は問題 2.1 の解 $\overline{1:}$if
en return. 枝刈りでもある$\epsilon\leq\langle f_{w},$$\chi_{a}\rangle_{\mu}$$A$

とき $a\in L$$f(\alpha\epsilon)$

$1$

$L$

$\overline{S}_{l}^{f}(\alpha, \epsilon)<e^{l}/2th$口

2: else if $|\alpha|=n$ then3. else EKM

3.2

前節で示した帰着より以下では問題 3.2 について議論する．疎なランダム線形符号のに関連した分布2:

ゴリズムによってクエリー効率的に解くことが出来$KM$ アルゴリズムを，より一ない．そこで我々は，$\sum_{\alpha’\in F_{2}^{n-k}}\langle f,$ $\chi_{\alpha a}\rangle_{\mu}^{2}$

ようにすると$\{\chi_{a}\}_{a\in F_{2}^{n}}$1

半内積$\not\in$の異なる二つのベクトルの直交

$T$

$\mu$

$J$

拡張 $KM$ アルゴリズムの正当性となる分布$2^{-\Omega(n)}$

$\mu$

につい

, 任意の $f:F_{2}^{n}arrow[-1,1],$ $\epsilon\in(0,1)$ に対してー数

$O(n\epsilon^{-3l}\ln(n/\epsilon))$,

リストサイズ$O(1/\epsilon^{l})$で$(a, b\in F_{2}^{n})$で7fl 題 32 の解を出力する．
$|$

$|$

$l$

を新たに導入した．ここで は偶数のパラメータである．
$l=2$ の場
合はと一致する．次見積もり関数においてパラメータ は，絶対値の大きな半内積と小さな半内積の差をどのぐらい強調するかを制御する． を大きくすることはアルゴリズムの性能を下げる向きに働くが，疎なランダム線形符号に対しては は高々定$=$$\epsilon$$|)$

半内積で現れづらいことに起因している．この問題を解決するために我々は，次見積もり$\chi_{\alpha\alpha’}\rangle_{\mu}^{l}$$\rho(\mu)$

$f$

$\mu$

$S_{l}( \alpha)=\sum_{\alpha’\in F_{2}^{n-k}}\langle f,$

理 3.4.

](空列，) を動作させると定数確率以上でクエ
EKM

性が弱く， と近い Fourier 基底ベクトルと遠いも関数

for $i\in[m]$$\frac{1}{m}\sum_{i}\prod_{j=1}^{l}f(z^{(i,j)})\chi_{\alpha}(\sum_{j=1}^{l}z^{(i,j)_{\leq k}})$

本節では次の定理を示す．

$f$

のとの差が

$f_{(\alpha 1,\epsilon)}.$という条件判定をクエリー効率的に近似することが出来ない．それは
の下では

3.3

$S_{2}(\alpha)=$と変更することであるが，この$S_{2}(\alpha)<\epsilon^{2}$, EKM$(z^{(i,1)}, \ldots , z^{(i,l)})arrow\mu|_{\leq k}^{l}$3: returnに対する問題 3.2 を解くものに拡張する．考えられる単純な拡張は見積もり関数をを出力．

$\frac{A1gorithm2\overline{S}_{l}^{f}(\alpha,\epsilon)}{1:marrow O(\epsilon^{-2l}\ln(n/\in)),karrow|\alpha|}$を含む $\mu=U_{n}$ でない場合の問題 3.2 は $KM$ アル$\mu$$\alpha$$)$4: end if

拡張 $KM$ アルゴリズムの構成

般的な分布$f_{(\alpha 0,\epsilon)}$

$($

ここで

$\rho(\mu)$$:= \max_{a\neq b}|\langle\chi$。

$\chi_{b}\rangle_{\mu}|$

$,$

$l$

$S_{2}$

り，この量が小さいほど， 半内積において異な$\mathfrak{B}$$\angle\backslash$$\mu$: Fourier 基底ベクトル同士の直交性が強いという$l$$\delta$$l$とができる．

$\rho(\mu)=2^{-\Omega(n)}$$\overline{c}$$(\backslash$

$l$

$npr$
$\not\in$$l$

数で十分であることを示すことができる．すぐに分かるように，$a\in F_{2}^{n}$がばそのすべての接頭辞立つ．ゆえに$\epsilon\leq|\langle f,$$\alpha$$S_{l}(\alpha)<\epsilon^{l}$$\chi_{a}\rangle_{\mu}|$についてを満たすなら$\epsilon^{l}\leq S_{l}(\alpha)$が成りを枝刈り条件として用いることが出来る．

す．ここで，与えるオラクルを右肩につけて表して
$KM$
いる．

ついて，

$\grave{}\grave{}$$\frac{-}{\frac{-}{\beta}}r$$\frac{-}{\overline{\overline{\beta}}}$明．定義よりは$\max_{a\neq b}|\langle\chi_{a},$$\chi_{b}\rangle_{\mu}|$つまり

bias $(C)$ に等しい．
が疎なランダム線形符号のときには，ある定数$c>0$ をが存在して十分大きなすべての

$c$

$n$

について

を満たす．従って定理 2.2以上の確率では bias $(C)\leq$$2^{-n/2c}n=2^{-\Omega(n)}$で抑えられる．口$f$$H\backslash$$X$似を用いる，この近似値は Algorithm 2 で定義されるが計算する．アルゴリズム中の分布 良ん$\rho(\mu)$$\max_{a\neq b}|1/2-\Delta(c(a), c(b))|=$$n$号語長 $N$ はのときと同じように，枝刈り評価をクエ」 り
リー効率的に行うために，EKM は の代わりに近 2$S_{l}$$\mu$

以上の確率で $\rho(\mu)=2^{-\Omega(n)}$fO 成り立つ
$j$

$c$
$C$

拡張 $KM$ アルゴリズム EKM を Algorithml に示

題 3.5. 疎なランダム線形符号に関連した分布$1-2^{-\Omega(n)}$$f$$f_{\overline{L}}$という条件は次の命に由来するものである．

$\Pi E$$\ovalbox{\tt\small REJECT}^{B}$$N\geq 2^{n/c}$$1-2^{-\Omega(n)}$$\rho(\mu)$

定理 3.4 が成り立ったとすると補題 3.3 と主\Sの定義は後述する．張 3.5 から定理 3.1 が成り立つことが示される．
以 降では定理 3.4 を示すための議論が続くが，ま$\overline{S}_{l}^{f}(\alpha)$

$\mu$

$J$

$L^{\backslash }A$114の近似値を計算することを たとき，EKMf(空列，) は 「 で成功した」 といずはじめに， が$Y^{(l)}iid\sim\mu$示す．
とする．また，これら い，文字列の集合 に対して． のすべての要$Y\sim\mu^{(l)}$を用意する． 素で成功したという意味で EKM (空列，) は 「と互いに独立な確率変数$\overline{S}_{l}$$S_{l}$$\epsilon$$Y^{(1)},$

$S$

$S$

$\ldots,$

$f$

$S$

$\epsilon$$(F_{2}^{n})^{l}$上の分布で成功した」 ということにする．EKM
で定め， の実行において EKMが呼び出されたようを $\mu|_{\leq k}^{l}(z^{(1)}, \cdots, z^{(l)})=$$\mu|_{\leq k}^{\iota}$$Pr[\bigwedge_{i=1}^{l}Y^{(i)}=z^{(i)}|\sum_{i=1}^{l}Y^{(:)_{>k}}=0]$$f(空列, \epsilon)$$f(\alpha,\epsilon)$

なの集合を VISIT とおく．空列もこの集合にとする．そして
VISIT のうちと定義する．次の 含めることとする．

$(Z^{(1)}, \cdots, Z^{(l)})\sim\mu|_{\leq k}^{l}$$E_{l}(\alpha)$$:=$$\alpha$$E[\prod_{i=1}^{l}f(Z^{(i)})\chi_{\alpha}(\sum_{i=1}^{l}Z^{(i)_{\leq k}})]$

補題 3.6 は$S_{l}(\alpha)$を$E_{l}(\alpha)$$\alpha$に十分近くできることを主張するものである．

$\overline{S}_{\iota}^{f}(\alpha, \epsilon)$

く．さらに $k=0,1,$$SURVIVE_{k}$VISIT$\ldots,$$b$の $k\leq n,$ $\alpha\in\{0,1\}^{k}$ に対してある定数 $l>0$ が存,$\leq$

が成り立ったものの集合を SURVIVE とお$\cap F_{2}^{k},$補題 3.6. $\rho(\mu)=2^{-\Omega(n)},$ $1/\epsilon=2^{o(n)}$ のとき，任意$\epsilon^{l}/4$

$\in$

VISIT

$\leq k$

$:=$

$n$

$VISIT_{k}:=$に対して，

SURVIVE, SURVIVE$\cap F_{2}^{k}$$:=$$\bigcup_{i\leq k}VISIT_{i}$と$:=$$\leq k$SURVIVE, とする．
次の補題はアルゴリズムの成功確率を保証するも$\bigcup_{i\leq k}$

在して，$|S_{l}(\alpha)-E_{l}(\alpha)|\leq\epsilon^{l}/8.$

証明．

$S_{l}(\alpha)$$2^{n}\langle f^{[\mu,l]},$すなわち$\sum_{\alpha\in F_{2}^{n-k}}\langle f^{[\mu,l]},$$\chi_{\alpha\alpha’}\rangle_{\mu^{\langle l)}}$に等しく，$2^{n}Pr[Y_{>k}$$\chi_{\alpha}\cdot\delta_{n-k\rangle_{\mu^{(l)}}}$

は， のである．
$=$

補題 3.7. 定数確率以上で EKM (空列，) は VISIT$f$$\epsilon$と変形できるの$0]E[f^{[\mu,1]}(Y)\chi_{\alpha}(Y\leq k)|Y_{>k}=0]$

で $S_{l}(\alpha)=2^{n-k}Pr[Y_{>k}=0]E_{l}(\alpha)$ が成り立つ．しで成功する．
この補題を示すための準備として，先に主張 3.8,

たがって $|Pr[Y_{>k}=0]-1/2^{n-k}|\leq 2^{-n}\epsilon^{l}/8$ を示せ

ばよい．左辺の 2 乗は，えられる．Parseval の等式とで上から抑

$2^{n}\Vert\mu^{(1)}-U_{n}\Vert_{2}^{2}$$U_{n}=\chi_{0^{\mathfrak{n}}}/2^{n}$

を使う

と，

$\Vert\mu^{(1)}-U_{n}\Vert_{2}^{2}=\sum_{。\in\{0,1\}^{\mathfrak{n}}}\langle\mu^{(l)}-Xg_{-,\chi_{a}\rangle^{2}=}^{\mathfrak{n}}2^{\mathfrak{n}}$$\chi$

主張 3.8.

一方，$\chi_{a}\rangle^{2}$

$a$

について

$0^{n}$$\neq$$\epsilon$

字列とすると，$\epsilon^{l}/4\leq S_{l}(\alpha)$

であり，さらに$\rangle|\leq 2^{-n}\rho(\mu^{(l)})$。

が成り立つ．したがって $|Pr[Y_{>k}=0]-1/2^{n-k}|\leq\rho(\mu)^{l}$よりある定数 $d>0$ がである．ここで，証明．補題 3.6 よりである．を定数$l$$\lambda>0$にとると，き，十分大きなすべての$2^{n}\rho(\mu)^{l}\leq 2^{-\lambda n/d}$

$n$

$n$

について，

であり，

$\epsilon=2^{-o(n)}$のとについて $\rho(\mu)^{l}\leq 2^{-n}\epsilon^{l}/8$となるから成り立つ．口

また，

とおくと次

の主張が成り立つ．
主張 3.9. 任意の $k\in[n]$ について，VISIT
功したとき$\leq k$$A_{k}(\epsilon^{l})\subseteq SURVIVE_{k}\subseteq A_{k}(\epsilon^{l}/4)$

で成

.

口

証明． についての帰納法で示す．
$k$

$k$

以降では
を

$-$

$A_{k}(\theta):=-\{\alpha\in F_{2}^{k}|\theta\leq S_{l}(\alpha)\}$$\rho(\mu)\leq$

で $l\geq d+\lambda$ を満たす値$|\overline{S}_{l}^{f}(\alpha, \epsilon)-S_{l}(\alpha)|\leq|\overline{S}_{l}^{f}(\alpha, \epsilon)$$E_{l}(\alpha)|\leq\epsilon^{l}/4$$E_{l}(\alpha)|+|S_{l}(\alpha)$$\rho(\mu)=2^{\Omega(n)}$存在して，十分大きなすべての.

$\rho(\mu^{(l)})=$$\max_{a\neq 0^{n}}E[\chi_{a}(Y^{(1)})]\cdots E[\chi_{a}(Y^{(1)})]\leq\rho(\mu)^{l}$$2^{-n/d}$

を EKM(空列，) が成功した任意の文$\alpha$$\epsilon^{l}\leq S_{t}(\alpha)\Rightarrow\epsilon^{l}/2\leq\overline{S}_{l}(\alpha)\Rightarrow$$\sum_{。\neq 0^{\mathfrak{n}}}\langle\mu^{(l)},$$|\langle\mu^{(1)},$

主張 3.9 および主張 3.10 を示す．

$\mu$

を $\rho(\mu)=2^{-\Omega(n)}$ である$2^{n}\rho(\mu)^{\iota}<\epsilon^{l}/8$が成り立つ定数$l\ovalbox{\tt\small REJECT}_{\overline{\llcorner}}$に限定し， き，VISIT
$l$

$\mu$

固定して議論

を進める．

れに加えて

$S_{l}^{f}(\alpha, \epsilon)$

も$\overline{S}_{l}(\alpha)$$E_{l}(\alpha)$

は$E_{l}(\alpha)$に近い．そに近くすることがでとも近いといえる．そこきれば，で EKM (空列，) の実行で呼び出された$\overline{S}_{l}^{f}(\alpha, \epsilon)$$S_{l}(\alpha)$$f$$\overline{S}_{l}^{f}(\alpha, \epsilon)$$\epsilon$の結果が$|\overline{S}_{l}^{f}(\alpha, \epsilon)-E(\alpha)|$$\leq$$\epsilon^{l}/8$

を満たし

$0$

のと

{空列} で成功したとすると，主張 3.8 より主張の包含関係が成り立つ．次に $k=$$k’$

補題 3.6 が示すように$\leq k=$$=$と$<n$ で主張が成り立つと仮定する．する

$1$

$-k$

$=$

$k’$

について VISIT$\leq k$で成功するとき，が成り立$A_{k-1}(\epsilon^{l})\subseteq SURVIVE_{k-1}\subseteq A_{k-1}(\epsilon^{\iota}/4)$

つ．

$\alpha\in A_{k}(\epsilon^{l})$より$\alpha$の長さ$|\alpha|$

を任意に取ると，$S_{l}(\cdot)$

1 の接頭辞$\alpha’$$A_{k-1}(\epsilon^{l})\subseteq SURVI\overline{V}E_{k}\subseteq VISIT_{k}$

の単調性

について

$\alpha’\in$となる．したがっ115て$\alpha$で成功するので主張 3.8 より $\alpha\in SURVIVE_{k}$となる．つまり$A_{k}(\epsilon^{l})\subseteq SURVIVE_{k}$である．今度

は $\alpha\in SURVIVE_{k}\subseteq VISIT_{k}$ を任意に取ると成功するので主張 3.8 より$\epsilon\leq\langle f,$$\alpha\in A_{k}(\epsilon^{l}/4)$$\alpha$$A_{n}(\epsilon^{l})$$\chi_{a}\rangle_{\mu}$を満たすすべての$a\in F_{2}^{n}$ては，主張 3.9 より，

で$L\subseteq A_{n}(\epsilon^{l}/4)$となる．口について $a\in$であるから $a\in L$ である．リストサイズについであり，主張 3.10を用いれば $|L|\leq|A_{n}(\epsilon^{l}/4)|=O(1/\epsilon^{l})$ . 最後にクエについリー数であるが，主張 3.9 より，$k=0,$てである．主張 3.10 から，

主張 3.10. $|A_{k}(\theta)|=O(1/\theta)$ .

$\ldots,$$n$$SURVIVE_{k}\subseteq A_{k}(\epsilon^{l}/4)$

証明．

とする．

$Y\sim\mu^{(l)}$$|A_{k}(\theta)|\theta$

は$|VISIT_{k}|=2|SURVIVE_{k-1}|\leq$$O(1/\epsilon^{l})$であり，VISIT$|$$|$$\leq$2SURVIVE $k-1=$$(n’+1)O(1/\epsilon^{l})$$=$が呼ばれる回数もことなるから，
内部では $ml=$の量で上から抑えられる．

$O(n/\epsilon^{l})$$\sum_{\alpha\in A_{k}(\theta)}S(\alpha)\leq\sum_{\alpha\in\{0,1\}^{k}}\langle f^{[\mu,l]},$ $\sum_{\alpha’}\chi_{\alpha\alpha’\rangle_{\mu^{(\iota)}}}$$\overline{S}_{l}^{f}(\cdot, \epsilon)$$\overline{S}_{l}^{f}(\cdot, \epsilon)$$O(\epsilon^{-2l}\ln(n/\epsilon))$$= \langle f^{[\mu,l]},\sum_{a\in\{0,1\}^{n}}\chi_{a}\rangle_{\mu^{(l)}}=2^{n}\langle f^{[\mu,l]},$$\delta_{n\rangle_{\mu^{(l)}}}$

回クエリーが行われるから，全体で行われる $f$ へのクエリー数は$O(n\epsilon^{-3l}\ln(n/\epsilon))$

下であることがわかる$=2^{n}Pr[Y=0]f^{[\mu,l]}(0)\leq 2^{n}Pr[Y=0]$

で抑えられ，右辺は補題 3.6 の証明の後半と同様の議論により $1+\epsilon^{l}/4=0(1)$ 7!抑えられ 6.

$*\vee’$$\square$

回以
口

考文献

[1] O. Goldreich and L.A. Levin. hard-core predicate for all one-way functions. In Proc. STOC
$H6$
補題 3.7 の証明． ffding の不等式を用いると，’89, pp. 25-32, 1989.
が失敗する確率は $2\exp\{-\epsilon^{2l}m_{l}/32\}=:q$[2] T. Kaufman and M. Sudan. Sparse random lin$VISIT_{k}$で抑えられる．各 $k\in\{0, \ldots, n\}$ について，
ear codes are locally decodable and testable. In
で成功するのは $|VISIT_{k}|$ 回実行されるがProc. FOCS ’07, pp. 590-600, 2007.
$A$

以上を用いて補題を示そう．

$\overline{S}_{l}^{f}(\cdot, \epsilon)$$\overline{S}_{l}^{f}(\cdot, \epsilon)$

すべて成功するときである．和集合上界を用いれば$VISIT_{k}$で失敗する確率は $|VISIT_{k}|q$ で上から抑えられる．VISIT$\leq k-1$

で成功したと仮定する．このとき主張 3.9 より SURVIVE

5. $VISIT_{k}$$=$$k-1\subseteq A_{k-1}(\epsilon^{l}/4)$$\{\alpha 0, \alpha 1 \alpha \in SURVIVE_{k-1}\}$であることと主張

3.10 にょり$2|SURVIVE_{k-1}|$$2|A_{k-1}(\epsilon^{l}/4)|$$\leq$$VISIT_{i-1}$$O(n/\epsilon^{l})q$

で成功

で成功]

$]$

$\prod_{i=1}^{n}Pr[VISIT_{i}$$\geq$$=$$=$$O(1/\epsilon^{l})$

$=$

で成功

$(1-O(1/\epsilon^{l})q)^{n+1}$

が成り立つ．右辺は

$|$

$1-$

$m=O(\epsilon^{-2l}\ln(n/\epsilon))$口

定理 3.4 の証明．補題 3.7 より定数確率以上でEKM (空列，) は VISIT で成功する．以下ではEKM $f(空列, \epsilon)$ が VISIT で成功したと仮定する．
は $SURVIVE_{n}$ に等し . 主張 3.9 より$f$$\epsilon$$L$$\mathfrak{h}\backslash \prime$[5] M. Sudan. List decoding: Algorithms and applications. SIGA CT News 31: 16-27, 2000.
$[I$$\geq$

を満たす十分大きな $m$ にょり任意の定数確率以上にすることが出来る[4] E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. SIAM
J. Comput. 22(6): 1331-1348, 1993.
$[$$|VISIT_{k}|$となる．以上から，Pr[VISIT で成功]
$Pr[VISIT_{0})$であ[ S. Kopparty and S. Saraf. Local list-decoding[3]
and testing of random linear codes from higherror. In Proc. STOC 70, pp. 417-426, 2010.

$A_{n}(\epsilon^{l})\subseteq L.$[6] A. Blum, A. Kalai, and H. Wasserman. Noisetolerant learning, the parity problem, and thestatistical query model. In Proc. of STOC 00,
pp. 435-440, 2000.
$[($