論文の概要: Amortized Locally Decodable Codes

• arxiv url: http://arxiv.org/abs/2502.10538v1
• Date: Fri, 14 Feb 2025 20:10:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-18 14:07:55.707025
• Title: Amortized Locally Decodable Codes
• Title（参考訳）: Amortized Locally Deodable Codes
• Authors: Jeremiah Blocki, Justin Zhang,
• Abstract要約: 暗号設定において局所的に復号可能な符号について検討する。 定常速度, 誤差耐性, 定位局所性といったトリフェクタを達成できることが示される。
• 参考スコア（独自算出の注目度）: 7.824613841086317
• License:
• Abstract: Locally Decodable Codes (LDCs) are error correcting codes that admit efficient decoding of individual message symbols without decoding the entire message. Unfortunately, known LDC constructions offer a sub-optimal trade-off between rate, error tolerance and locality, the number of queries that the decoder must make to the received codeword $\tilde {y}$ to recovered a particular symbol from the original message $x$, even in relaxed settings where the encoder/decoder share randomness or where the channel is resource bounded. We initiate the study of Amortized Locally Decodable Codes where the local decoder wants to recover multiple symbols of the original message $x$ and the total number of queries to the received codeword $\tilde{y}$ can be amortized by the total number of message symbols recovered. We demonstrate that amortization allows us to overcome prior barriers and impossibility results. We first demonstrate that the Hadamard code achieves amortized locality below $2$ -- a result that is known to be impossible without amortization. Second, we study amortized locally decodable codes in cryptographic settings where the sender and receiver share a secret key or where the channel is resource-bounded and where the decoder wants to recover a consecutive subset of message symbols $[L,R]$. In these settings we show that it is possible to achieve a trifecta: constant rate, error tolerance and constant amortized locality.
• Abstract（参考訳）: ローカル復号コード(英: Locally Deodable Codes、LDC)は、メッセージ全体を復号することなく、個々のメッセージシンボルを効率よく復号できる誤り訂正符号である。 残念ながら、既知のLCC構造は、レート、エラー耐性、ローカリティの間のサブ最適トレードオフを提供しており、デコーダが受信したコードワード $\tilde {y}$ に対して、元のメッセージ $x$ から特定のシンボルを復元するために、エンコーダ/デコーダがランダム性を共有したり、チャンネルがリソースのバウンドされた場所を共有するような緩和された設定でも、デコーダが実行しなければならないクエリの数である。 我々は、ローカルデコーダが元のメッセージ$x$の複数のシンボルを復元したい場合、受信したコードワード$\tilde{y}$に対するクエリの総数は、回収されたメッセージシンボルの総数によってアモータイズできる、Amortized Locally Deodable Codesの研究を開始する。 我々は、償却によって、以前の障壁や不可能な結果を克服できることを実証する。 私たちはまず、アダマール符号が2ドル以下で償却された局所性を達成することを実証した。 次に、送信側と受信側が秘密鍵を共有したり、チャンネルがリソースバウンドされたり、デコーダがメッセージシンボルの連続的なサブセットを$[L,R]$で回収したい場合の暗号化設定において、局所的復号化コードについて検討する。 これらの設定では、定レート、エラー耐性、定位局所性というトリフェクタを達成できることが示される。

関連論文リスト

• Threshold Selection for Iterative Decoding of $(v,w)$-regular Binary Codes [84.0257274213152]
  繰り返しビットフリップデコーダは、sparse $(v,w)$-regular符号の効率的な選択である。 閉形式モデルに基づくしきい値決定のための具体的な基準を提案する。
  論文  参考訳（メタデータ） (2025-01-23T17:38:22Z)
• Decoding Quantum LDPC Codes using Collaborative Check Node Removal [0.0]
  協調的な手法を用いて反復デコーダの性能を向上させるための戦略を提案する。 我々は、ビット分離の概念を使い、それをqubit分離に一般化する。 これにより、QLDPC符号の有害な構成に対してデコーダの性能を分析し改善する指標が得られる。
  論文  参考訳（メタデータ） (2025-01-14T11:41:45Z)
• Collective Bit Flipping-Based Decoding of Quantum LDPC Codes [0.6554326244334866]
  可変次数-3(dv-3)QLDPC符号の繰り返し復号化による誤り訂正性能と復号遅延の両方を改善した。 我々の復号方式は、ビットフリップ(BF)デコーディングの修正版、すなわち2ビットビットフリップ(TBF)デコーディングを適用することに基づいている。
  論文  参考訳（メタデータ） (2024-06-24T18:51:48Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。 本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
  論文  参考訳（メタデータ） (2024-01-30T11:40:24Z)
• Fault-Tolerant Quantum Memory using Low-Depth Random Circuit Codes [0.24578723416255752]
  低深さランダム回路符号は、量子誤り訂正に望ましい多くの特性を有する。 1次元ランダム回路符号の符号化状態を作成するための耐故障性蒸留プロトコルを設計する。 数値シミュレーションにより,提案プロトコルはエラー率を最大2%の誤差率で補正できることを示す。
  論文  参考訳（メタデータ） (2023-11-29T19:00:00Z)
• Good Gottesman-Kitaev-Preskill codes from the NTRU cryptosystem [5.497441137435869]
  我々は,いわゆるNTRU暗号系の暗号解析から得られた,ランダムなGottesman-Kitaev-Preskill(GKP)符号のクラスを導入する。 NTRU-GKP符号の派生型は、変位ノイズモデルの復号化がNTRU暗号システムの復号化と等価であるという付加的な性質を持つ。 この構造は、GKPコードがどのように古典的誤り訂正、量子誤り訂正、およびポスト量子暗号の側面を橋渡しするかを強調している。
  論文  参考訳（メタデータ） (2023-03-04T14:39:20Z)
• Adversarial Neural Networks for Error Correcting Codes [76.70040964453638]
  機械学習(ML)モデルの性能と適用性を高めるための一般的なフレームワークを紹介する。 本稿では,MLデコーダと競合する識別器ネットワークを組み合わせることを提案する。 我々のフレームワークはゲーム理論であり、GAN(Generative Adversarial Network)によって動機付けられている。
  論文  参考訳（メタデータ） (2021-12-21T19:14:44Z)
• Dense Coding with Locality Restriction for Decoder: Quantum Encoders vs. Super-Quantum Encoders [67.12391801199688]
  我々は、デコーダに様々な局所性制限を課すことにより、濃密な符号化について検討する。 このタスクでは、送信者アリスと受信機ボブが絡み合った状態を共有する。
  論文  参考訳（メタデータ） (2021-09-26T07:29:54Z)
• KO codes: Inventing Nonlinear Encoding and Decoding for Reliable Wireless Communication via Deep-learning [76.5589486928387]
  ランドマークコードは、Reed-Muller、BCH、Convolution、Turbo、LDPC、Polarといった信頼性の高い物理層通信を支える。 本論文では、ディープラーニング駆動型(エンコーダ、デコーダ)ペアの計算効率の良いファミリーであるKO符号を構築する。 KO符号は最先端のリード・ミュラー符号と極符号を破り、低複雑さの逐次復号法で復号された。
  論文  参考訳（メタデータ） (2021-08-29T21:08:30Z)
• Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders [77.34726150561087]
  Restriction Decoderは、対応するトーリックコード復号が成功した場合に限り、カラーコードのエラーを修正する。 ビットフリップと位相フリップの雑音に対して、2次元、3次元のカラーコードに対する制限デコーダ閾値を数値的に推定する。
  論文  参考訳（メタデータ） (2019-05-17T17:41:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。