ローカルでテスト可能なコード

ローカルでテスト可能なコードは、文字列の小さなビット数 (多くの場合は一定) を調べることで、文字列がそのコード内の単語であるかどうかを判断できるエラー訂正コードの一種です。状況によっては、データ全体をデコードしなくてもデータが破損しているかどうかを知ることができれば、適切な対応を取ることができます。たとえば、通信では、受信側が破損したコードに遭遇した場合、データの再送信を要求できるため、そのデータの精度を高めることができます。同様に、データ ストレージでは、これらのコードにより、破損したデータを回復して適切に書き直すことができます。

対照的に、ローカルにデコード可能なコードは、コードワードの少数のビットを使用して、元の情報を確率的に復元します。エラーの割合によって、デコーダが元のビットを正しく復元する可能性が決まりますが、すべてのローカルにデコード可能なコードがローカルにテスト可能であるわけではありません。^[1]

明らかに、有効なコードワードはコードワードとして受け入れられるべきですが、コードワードではない文字列は 1 ビットだけずれている可能性があり、その場合は多くの (定数以上) プローブが必要になります。これを考慮して、文字列が少なくとも設定されたビット数ずれている場合にのみ、テストの失敗が定義されます。これは、冗長性を追加することで、コードのワードが入力文字列よりも長くなければならないことを意味します。

2つの文字列間の距離を測定するには、ハミング距離が使用されます。

${\displaystyle \Delta (x,y)=|\{i:x_{i}\neq y_{i}\}|}$

文字列とコードの距離は次のように計算されます。 ${\displaystyle w}$${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$

${\displaystyle \Delta (w,C)=\min _{x}\{\Delta (w,C(x))\}}$

相対距離はビット数の割合として計算されます

${\displaystyle \delta (x,y)=\Delta (x,y)/n{\text{ および }}\delta (w,C)=\Delta (w,C)/n}$

入力にランダムアクセスし、最大で非適応的なクエリを実行し、次の条件を満たすチューリングマシンMが存在する場合、コードは-local- testableと呼ばれます。 ^[2]${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$${\displaystyle q}$${\displaystyle \delta}$${\displaystyle w}$${\displaystyle q}$${\displaystyle w}$

• 任意のおよびに対して、。言い換えれば、M は C の任意のコードワードへのアクセスを受け入れます。${\displaystyle x\in \{0,1\}^{k}}$${\displaystyle w=C(x)}$${\displaystyle Pr[M^{w}(1^{k})=1]=1}$
• となる場合、 M は少なくとも半分の時間、C から遠い文字列を拒否する必要があります。${\displaystyle \in \{0,1\}^{n}}$${\displaystyle \delta (w,C)>\delta }$${\displaystyle Pr[M^{w}(1^{k})=1]\leq 1/2}$${\displaystyle \delta}$

また、コードのレートは、メッセージの長さとコードワードの長さの比率です。

${\displaystyle r={\frac {|x|}{|C(x)|}}}$

線形サイズの局所的にテスト可能なコードが存在するかどうかは未解決の問題であるが、「ほぼ線形」であると考えられる構造がいくつかある: ^[3]

1. 多項式は任意に線形に近い。任意のに対して。${\displaystyle \epsilon >0}$${\displaystyle n=k^{1+\epsilon }}$
2. 形式の関数。ここで は0 に向かう関数です。これにより、k が増加するにつれて n​​ は線形に近づきます。例: ${\displaystyle n=k^{1+\epsilon (k)}}$${\displaystyle \epsilon (k)}$
   • ${\displaystyle 1/\log \log k}$
   • ${\displaystyle 1/(\log k)^{c}}$一部の人にとって${\displaystyle c\in (0,1)}$
   • ${\displaystyle \exp((\log \log \log k)^{c})/\log k}$のために${\displaystyle c\in (0,1)}$

これらは両方とも、クエリの複雑さが一定で、任意のに対して のようなバイナリアルファベットであっても達成されています。次のほぼ線形の目標は、多重対数係数まで線形です。この制約を満たす線形テスト可能なコードをまだ誰も思いついていません。^[3]${\displaystyle n=k^{1+1/(\log k)^{c}}}$${\displaystyle c\in (0,1)}$${\displaystyle n={\text{poly}}(\log k)*k}$

2021年11月に2つのプレプリントで、定数レート、定数距離、定数局所性を持つ局所的にテスト可能なコードである「-LTC」の最初の多項式時間構築が報告されました^{[4 ] [ 5] [6 ] [7]}。 ${\displaystyle c^{3}}$${\displaystyle r}$${\displaystyle \delta}$${\displaystyle q}$

ローカルにテスト可能なコードは、確率的にチェック可能な証明(PCP)と多くの共通点があります。これは、その構成の類似性から明らかです。どちらも、大きな文字列へのランダムな非適応クエリが与えられ、受け入れる場合は確率 1 で受け入れる必要があり、そうでない場合は半分以上の確率で受け入れる必要があります。主な違いは、PCP は が存在する場合に受け入れることに関心があるということです。一方、ローカルにテスト可能なコードは、がコードの一部である場合に受け入れます。PCP 証明がローカルにテスト可能なコードをエンコードすると想定すると、多くの問題が発生する可能性があります。たとえば、PCP 定義では無効な証明については何も述べられておらず、無効な入力についてのみ述べられています。 ${\displaystyle q}$${\displaystyle x}$${\displaystyle w}$${\displaystyle M^{w}(x)=1}$${\displaystyle w}$

この違いにもかかわらず、ローカルテスト可能なコードとPCPは十分に類似しているため、証明者は一方を構築する過程で他方を構築することがよくあります。^[8]

最も有名な誤り訂正符号の 1 つであるアダマール符号は、局所的にテスト可能な符号です。符号語 x は、線形関数(mod 2) としてアダマール符号にエンコードされます。これには、この関数の結果をすべての可能な y に対してリストアップする必要があり、入力よりも指数的に多くのビットが必要になります。文字列 w がアダマール符号の符号語であるかどうかをテストするには、エンコードされた関数が線形かどうかをテストするだけです。これは、x と y が一様ランダムベクトルであるかどうかを確認するだけです (ここで、 はビット単位の XORを表します) 。${\displaystyle f(y)={\sum _{i}{x_{i}y_{i}}}}$${\displaystyle w(x)\oplus w(y)=w(x\oplus y)}$${\displaystyle \oplus}$

任意の有効なエンコード に対して、この式が真であることは簡単にわかります。これは線形関数の定義だからです。しかし、やや難しいのは、C から遠い文字列が に関してその誤差の上限を持つことを示すことです。1 つの上限は、3 つのプローブのうち 1 つが誤った結果を出す確率を近似するという直接的なアプローチによって見つかります。 A、B、C を、、が誤っているイベントとします。E を、これらのうち 1 つが発生するイベントとします。これは次のようになります。 ${\displaystyle w}$${\displaystyle \delta}$${\displaystyle \delta}$${\displaystyle w(x)}$${\displaystyle w(y)}$${\displaystyle w(x\oplus y)}$

${\displaystyle {\begin{aligned}P(E)&\geq P(A\cup B\cup C)-3*P(A\cup B)\\&\geq 3*P(A)-3*P(A\cup B)-3*P(A\cup B)\\&\geq 3\delta -6\delta ^{2}\end{aligned}}}$

これは では機能しますが、その直後には になります。さらに作業を進めると、誤差が で制限されることがわかります。 ${\displaystyle 0<\delta \leq 5/16}$${\displaystyle 3\delta -6\delta ^{2}<\delta }$

${\displaystyle f(x)={\begin{cases}3\delta -6\delta ^{2}&:0\leq \delta \leq 5/16\\45/128&:5/16\leq \delta \leq 45/128\\\delta &:45/128\leq \delta \leq 1/2\end{cases}}}$

任意の に対して、偽陽性の確率は一定であるため、確率を1/2未満にするには、単純に一定回数チェックすればよい。^[3]${\displaystyle \delta }$

ロングコードは、非常に大きな爆発を伴う別のコードですが、ローカルでテスト可能です。入力が与えられると（これは ビットで表すことに注意）、入力の ビットを返す関数 がすべての可能なビット入力で評価され、コードワードはこれらの連結（長さ）になります。これをエラーありでローカルにテストする方法は、一様ランダム入力を選び、各ビットを反転する小さな可能性 で を設定することです。 の場合、関数をコードワードとして受け入れます。 がコードワードの場合、 が変更されない限り、これは の確率で受け入れられます。これは、コードワードが常に受け入れられるという要件に違反しますが、いくつかのニーズには十分かもしれません。^[9]${\displaystyle 0\leq i\leq 2^{k}}$${\displaystyle k}$${\displaystyle i^{th}}$${\displaystyle f_{i}(x)=x_{i}}$${\displaystyle 2^{k}}$${\displaystyle 0\leq x\leq 2^{2^{k}}}$${\displaystyle n=2^{2^{k}}}$${\displaystyle x}$${\displaystyle y=x}$${\displaystyle \mu >0}$${\displaystyle f}$${\displaystyle f(x)=f(y)}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x_{i}}$${\displaystyle 1-\mu }$

その他のローカルにテスト可能なコードには、リード・ミュラー コード(デコード アルゴリズムについてはローカルにデコード可能なコードを参照)、リード・ソロモン コード、ショート コードなどがあります。

• ギルバート・ヴァルシャモフ境界
• ハミングコード
• エクスパンダーコード

• 「ブレークスルー — 一定の速度、距離、局所性を備えたローカルでテスト可能なコード | Simons Institute for the Theory of Computing」. simons.berkeley.edu . 2021年10月6日。