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

• arxiv url: http://arxiv.org/abs/2406.12160v1
• Date: Tue, 18 Jun 2024 00:22:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 23:28:06.615853
• Title: Block Circulant Codes with Application to Decentralized Systems
• Title（参考訳）: ブロック循環符号と分散システムへの応用
• Authors: Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau,
• Abstract要約: C_textBC[mu,lambda,omega,rho]$ with blocklength $n=mu(rho+omega)$ and dimension $k=muomega$。 ローカルコードはすべて$cal C_textBC[mu,lambda,omega,rho]$は$[rho+lambdaomega,lambdaomega,rho+1]$ generalized Reed-Solomon (RS)である。
• 参考スコア（独自算出の注目度）: 12.014314088945968
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The structure of linear dependence relations between coded symbols of a linear code, irrespective of specific coefficients involved, is referred to as the {\em topology} of the code. The specification of coefficients is referred to as an {\em instantiation} of the topology. In this paper, we propose a new block circulant topology $T_{[\mu,\lambda,\omega]}(\rho)$ parameterized by integers $\rho \geq 2$, $\omega \geq 1$, $\lambda \geq 2$, and $\mu$ a multiple of $\lambda$. In this topology, the code has $\mu$ local codes with $\rho$ parity-check (p-c) constraints and a total of $\mu\rho$ p-c equations fully define the code. Next, we construct a class of block circulant (BC) codes ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$ with blocklength $n=\mu(\rho+\omega)$, dimension $k=\mu\omega$ that instantiate $T_{[\mu,\lambda,\omega]}(\rho)$. Every local code of ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$ is a $[\rho+\lambda\omega,\lambda\omega,\rho+1]$ generalized Reed-Solomon (RS) code. The overlap between supports of local codes helps to enhance the minimum distance $\rho+1$ to $2\rho+1$, without compromising much on the rate. We provide an efficient, parallelizable decoding algorithm to correct $2\rho$ erasures when $\lambda=2$. Finally, we illustrate that the BC codes serve as a viable alternative to 2D RS codes in protocols designed to tackle blockchain networks' data availability (DA) problem. In these protocols, every node in a network of light nodes randomly queries symbols from a codeword stored in full nodes and verifies them using a cryptographic commitment scheme. For the same performance in tackling the DA problem, the BC code requires querying a smaller number of symbols than a comparable 2D RS code for a fixed high rate. Furthermore, the number of local codes in the BC code is typically smaller, yielding a reduction in the complexity of realizing the commitment scheme.
• Abstract（参考訳）: 線形符号の符号付き記号間の線形依存関係の構造は、関係する特定の係数に関係なく、符号の {\em topology} と呼ばれる。 係数の仕様はトポロジーの {\em instantiation} と呼ばれる。 本稿では,新しいブロック循環トポロジーである$T_{[\mu,\lambda,\omega]}(\rho)$を整数でパラメータ化し,$\rho \geq 2$,$\omega \geq 1$,$\lambda \geq 2$,$\mu$ a multiple of $\lambda$を提案する。 このトポロジーにおいて、コードは$\mu$ローカルコードを持ち、$\rho$ parity-check (p-c) 制約を持ち、合計$\mu\rho$ p-c 方程式はコードを完全に定義している。 次に、ブロックサーキュラント(BC)コードのクラスを構成する。 ${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$ with blocklength $n=\mu(\rho+\omega)$, dimension $k=\mu\omega$ that instantiate $T_{[\mu,\lambda,\omega]}(\rho)$。 ローカルコードはすべて${\cal C}_{\text{BC}}[\mu,\lambda,\omega,\rho]$は$[\rho+\lambda\omega,\lambda\omega,\rho+1]$ Generalized Reed-Solomon (RS)コードです。 ローカルコードのサポート間のオーバーラップは、レートに多くの妥協を加えることなく、最小距離$\rho+1$から$2\rho+1$に拡張するのに役立ちます。 効率よく並列化可能なデコードアルゴリズムを提供し、$\lambda=2$のときに2$\rho$消去を補正する。 最後に、BCコードはブロックチェーンネットワークのデータ可用性(DA)問題に対処するために設計されたプロトコルにおいて、2D RSコードに代わる実行可能な代替手段として機能することを示す。 これらのプロトコルでは、光ノードのネットワーク内の各ノードは、全ノードに格納されたコードワードからランダムにシンボルをクエリし、暗号的なコミットメントスキームを用いて検証する。 DA問題に対処するのと同じパフォーマンスのために、BCコードは固定レートで同等の2D RSコードよりも少ない数のシンボルをクエリする必要がある。 さらに、BCコード内のローカルコードの数は典型的には小さく、コミットメントスキームを実現する複雑さが減少する。

関連論文リスト

• 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)

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

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