論文の概要: Amortized Locally Decodable Codes

• arxiv url: http://arxiv.org/abs/2502.10538v1
• Date: Fri, 14 Feb 2025 20:10:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-18 20:34:44.515245
• Title: Amortized Locally Decodable Codes
• Title（参考訳）: Amortized Locally Deodable Codes
• Authors: Jeremiah Blocki, Justin Zhang,
• Abstract要約: 暗号設定において局所的に復号可能な符号について検討する。 定常速度, 誤差耐性, 定位局所性といったトリフェクタを達成できることが示される。
• 参考スコア（独自算出の注目度）: 7.824613841086317
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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]$で回収したい場合の暗号化設定において、局所的復号化コードについて検討する。 これらの設定では、定レート、エラー耐性、定位局所性というトリフェクタを達成できることが示される。

関連論文リスト

• Polar Coding and Linear Decoding [0.0]
  2009年7月7日 IEEE Transactions on Information Theory, Vol. 55, No. 7 でアリカンが記述した極性符号化は通信のマイルストーンとなった。 極性符号は、情報を高容量チャネルと低容量チャネルに分散し、完全チャネル容量を達成する可能性を示す。
  論文  参考訳（メタデータ） (2025-07-25T22:23:14Z)
• 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)
• Degenerate quantum erasure decoding [7.6119527195998025]
  消去は、漏洩エラーに支配される物理システムにおける主要なタイプのエラーである。 我々は,最大自由度復号法(MLD)の下での量子符号の消去能力を示す。 本稿では,線形時間で動作し,安定化器符号の誤り縮退を利用した信念伝搬(BP)デコーダを提案する。
  論文  参考訳（メタデータ） (2024-11-20T18:02:05Z)
• Collective Bit Flipping-Based Decoding of Quantum LDPC Codes [0.6554326244334866]
  可変次数-3(dv-3)QLDPC符号の繰り返し復号化による誤り訂正性能と復号遅延の両方を改善した。 我々の復号方式は、ビットフリップ(BF)デコーディングの修正版、すなわち2ビットビットフリップ(TBF)デコーディングを適用することに基づいている。
  論文  参考訳（メタデータ） (2024-06-24T18:51:48Z)
• Decoding at the Speed of Thought: Harnessing Parallel Decoding of Lexical Units for LLMs [57.27982780697922]
  大規模言語モデルは、自然言語の理解と生成において例外的な能力を示した。 しかし、それらの生成速度は、その復号過程の本質的にシーケンシャルな性質によって制限される。 本稿では,データ駆動方式で実装された新しいデコーディング手法であるLexical Unit Decodingを紹介する。
  論文  参考訳（メタデータ） (2024-05-24T04:35:13Z)
• 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)
• Denoising Diffusion Error Correction Codes [92.10654749898927]
  近年、ニューラルデコーダは古典的デコーダ技術に対する優位性を実証している。 最近の最先端のニューラルデコーダは複雑で、多くのレガシデコーダの重要な反復的スキームが欠如している。 本稿では,任意のブロック長の線形符号のソフトデコードにデノナイズ拡散モデルを適用することを提案する。
  論文  参考訳（メタデータ） (2022-09-16T11:00:50Z)
• 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)

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

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