論文の概要: Block Circulant Codes with Application to Decentralized Systems

• arxiv url: http://arxiv.org/abs/2406.12160v2
• Date: Mon, 16 Dec 2024 04:33:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 13:48:33.630302
• Title: Block Circulant Codes with Application to Decentralized Systems
• Title（参考訳）: ブロック循環符号と分散システムへの応用
• Authors: Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau,
• Abstract要約: 我々は,分散消去復号化をサポートするブロック循環符号のファミリ[n,k,d]を開発する。 このコードは、ブロックチェーンネットワークのデータ可用性問題に対処するプロトコルで使用するのに理想的だ。
• 参考スコア（独自算出の注目度）: 12.014314088945968
• License:
• Abstract: In this paper, we design a family of $[n,k,d]$ block circulant codes that consist of many $[n_0 \ll n,k_0 \ll k,d_0]$ local codes and that satisfy three properties: (1) the code supports distributed erasure decoding, (2) $d$ can be scaled above $d_0$ by a given parameter, and (3) it is amenable to low complexity verification of code symbols using a cryptographic commitment scheme. These properties make the code ideal for use in protocols that address the data availability problem in blockchain networks. Moreover, the code outperforms the currently used 2D Reed-Solomon (RS) code with a larger relative minimum distance $(d/n)$, as desired in the protocol, for a given rate $(k/n)$ in the high-rate regime. The code is designed in two steps. First, we develop the topology, i.e., the structure of linear dependence relations among code symbols, and define it as the block circulant topology $T_{[\mu,\lambda,\omega]}(\rho)$. In this topology, there are $\mu$ local codes, each constrained by $\rho$ parity checks. The set of symbols of a local code intersects with another in a uniform pattern, determined by two parameters, namely the overlap factor $\lambda$ and the overlap width $\omega$. Next, we instantiate the topology, i.e., to specify the coefficients of linear dependence relations, to construct the block circulant codes ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$. Every local code is a $[\lambda\omega+\rho,\lambda\omega,\rho+1]$ generalized RS code. The block circulant code has $n=\mu(\rho+\omega)$, $k=\mu\omega$ and we show that $d=\lambda\rho+1$ under certain conditions. For $\lambda=2$, we prove that $d=2\rho+1$ always, and provide an efficient, parallelizable erasure-correcting decoder that fully recovers the codeword when there are $\leq 2\rho$ erasures. The decoder uses a novel decoding mechanism that iteratively recovers erasures from pairs of local codes.
• Abstract（参考訳）: 本稿では,多くの$[n_0 \ll n,k_0 \ll k,d_0]$ローカルコードからなるブロック循環コードのファミリーを設計し,(1)コードが分散消去デコーディングをサポートすること,(2)$d$を所定のパラメータで$d_0$以上スケール可能であること,(3)暗号コミットメントスキームを用いてコードシンボルの複雑さの検証を行うことができること,の3つの特性を満たす。 これらのプロパティは、ブロックチェーンネットワークのデータ可用性問題に対処するプロトコルで使用するのに理想的なコードである。 さらに、現在の2D Reed-Solomon (RS) コードは、プロトコルで望まれるような、より大きい相対的最小距離$(d/n)$で、ハイレートで与えられたレート$(k/n)$よりも優れている。 コードは2つのステップで設計されている。 まず、符号記号間の線形依存関係の構造であるトポロジーを開発し、それをブロック循環トポロジー $T_{[\mu,\lambda,\omega]}(\rho)$ と定義する。 このトポロジには$\mu$ローカルコードがあり、それぞれ$\rho$パリティチェックによって制約されている。 ローカルコードのシンボルのセットは、一様パターンで相互に交わり、オーバーラップ係数$\lambda$とオーバーラップ幅$\omega$という2つのパラメータによって決定される。 次に、トポロジー、すなわち線形依存関係の係数を定め、ブロック循環コードを構成するために、${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$をインスタンス化する。 すべてのローカルコードは$[\lambda\omega+\rho,\lambda\omega,\rho+1]$ 一般化RSコードである。 ブロック循環コードは$n=\mu(\rho+\omega)$, $k=\mu\omega$であり、ある条件下では$d=\lambda\rho+1$を示す。 $\lambda=2$の場合、$d=2\rho+1$が常にあることを証明し、$\leq 2\rho$消去があるときにコードワードを完全に復元する、効率的で並列化可能な消去デコーダを提供する。 デコーダは、一対のローカルコードから消去を反復的に回収する新しい復号機構を使用する。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Characterizing Quantum Codes via the Coefficients in Knill-Laflamme Conditions [3.980076328494117]
  量子誤り訂正(QEC)は、ノイズに対する量子情報の保護に不可欠である。 我々は, Knill-Laflamme (KL) 係数 $lambda_ij$ の構造を条件 $PE_idagger E_j P = lambda_ij P$ から検討する。
  論文  参考訳（メタデータ） (2024-10-10T14:38:15Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Performance Analysis of Quantum CSS Error-Correcting Codes via MacWilliams Identities [9.69910104594168]
  実用実装において最も重要なクラスの1つである安定化器符号の性能を解析する。 WEの知識と論理演算子解析を組み合わせた新しい手法を提案する。 大きなコードについては、$rho_mathrmL approx 1215 rho4$および$rho_mathrmL approx 663 rho5$ for the $[85,1,7]$および$[181,1,10]$Surface codesを提供します。
  論文  参考訳（メタデータ） (2023-05-02T10:19:02Z)
• CSS code surgery as a universal construction [51.63482609748332]
  連鎖複体間の写像を用いて,Calderbank-Shor-Steane (CSS) 符号間のコードマップを定義する。 鎖状錯体のカテゴリにおいて,特定のコリミットを用いたコード間のコード手術について述べる。
  論文  参考訳（メタデータ） (2023-01-31T16:17:25Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Divisible Codes for Quantum Computation [0.6445605125467572]
  可分符号は、符号語重みが1より大きい共通の因子を共有する性質によって定義される。 本稿では、論理ゲートによって変換される量子情報を保護するために、それらがどのように使用できるかを検討する。
  論文  参考訳（メタデータ） (2022-04-27T20:18:51Z)
• Distance bounds for generalized bicycle codes [0.7513100214864644]
  一般化自転車符号(英: Generalized bike codes, GB codes)は、二項循環行列からなる量子誤り訂正符号のクラスである。 我々は,行重4,6,8の2ビット符号化符号群において,ある素循環サイズのGB符号を網羅的に列挙した。 観測された距離スケーリングは、$A(w)n1/2+B(w)$と一致しており、$n$はコード長であり、$A(w)$は$w$で増加している。
  論文  参考訳（メタデータ） (2022-03-31T17:43:34Z)
• Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically [36.685393265844986]
  我々は,量子-Omega-Varshamovを有界に達成する量子誤り訂正符号の新たなファミリを構築する。 $mathscrQ$は$O(N)$とdeep $O(sqrtN)$の回路で非常に効率的に符号化できる。 $mathscrQ$は$O(sqrtN)$timeで並列に復号することもできる。
  論文  参考訳（メタデータ） (2021-07-12T03:27:30Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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