ローカルエラー訂正の限界を探る(Searching for the Limits of Local Error Correction)

ad

2024-04-30 カーネギーメロン大学

情報の伝達や変換には、多くの障害が伴います。無線通話では、言語に対応するビット列(0と1の連続)が壁を反射しながらルーターに到達し、途中でエラーや歪みが生じることがあります。
◆カーネギーメロン大学のプラヴェシュ・コータリ助教授とピーター・マノハル博士課程学生は、これらのエラーを訂正するアルゴリズムの改善に取り組み、数学的証明を通じてエラー訂正技術を微調整しています。
◆この研究は、情報を安全に共有するための暗号技術にも応用可能です。エラー訂正の基本的な方法は情報に冗長性を加えることで、CD-ROMなどのメディアでも使われています。これにより、本来の容量より少ないデータしか保存できないものの、物理的損傷があっても再生が可能になっています。

<関連情報>

線形3クエリ局所訂正符号の指数下界 An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

Pravesh K. Kothari, Peter Manohar
arXiv  Submitted on: 1 Nov 2023
DOI:https://doi.org/10.48550/arXiv.2311.00558

ローカルエラー訂正の限界を探る(Searching for the Limits of Local Error Correction)

Abstract

We prove that the blocklength n of a linear 3-query locally correctable code (LCC) L:Fk→Fn with distance δ must be at least n≥2Ω((δ2k(|F|−1)2)1/8). In particular, the blocklength of a linear 3-query LCC with constant distance over any small field grows exponentially with k. This improves on the best prior lower bound of n≥Ω~(k3) [AGKM23], which holds even for the weaker setting of 3-query locally decodable codes (LDCs), and comes close to matching the best-known construction of 3-query LCCs based on binary Reed-Muller codes, which achieve n≤2O(k1/2). Because there is a 3-query LDC with a strictly subexponential blocklength [Yek08, Efr09], as a corollary we obtain the first strong separation between q-query LCCs and LDCs for any constant q≥3.
Our proof is based on a new upgrade of the method of spectral refutations via Kikuchi matrices developed in recent works [GKM22, HKM23, AGKM23] that reduces establishing (non-)existence of combinatorial objects to proving unsatisfiability of associated XOR instances. Our key conceptual idea is to apply this method with XOR instances obtained via long-chain derivations, a structured variant of low-width resolution for XOR formulas from proof complexity [Gri01, Sch08].

1600情報工学一般
ad
ad
Follow
ad
タイトルとURLをコピーしました