Block Circulant Codes with Application to Decentralized Systems
- URL: http://arxiv.org/abs/2406.12160v1
- Date: Tue, 18 Jun 2024 00:22:20 GMT
- Title: Block Circulant Codes with Application to Decentralized Systems
- Authors: Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau,
- Abstract summary: We construct a class of block circulant codes $cal C_textBC[mu,lambda,omega,rho]$ with blocklength $n=mu(rho+omega)$ and dimension $k=muomega$.
Every local code of $cal C_textBC[mu,lambda,omega,rho]$ is a $[rho+lambdaomega,lambdaomega,rho+1]$ generalized Reed-Solomon (RS)
- Score: 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.
Related papers
- Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
Decentralized online convex optimization (D-OCO) aims to minimize a sequence of global loss functions using only local computations and communications.
We develop novel D-OCO algorithms that can respectively reduce the regret bounds for convex and strongly convex functions.
Our algorithms are nearly optimal in terms of $T$, $n$, and $rho$.
arXiv Detail & Related papers (2024-02-14T13:44:16Z) - On combinatorial structures in linear codes [0.0]
If the codes are classical we show instead that the $K_i$'s are $tildeOmegaleft(k/nright)$-expander.
In particular, we show that the BPT bound for classical codes is tight in all Euclidean dimensions.
arXiv Detail & Related papers (2023-09-28T13:03:41Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model.
For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits.
For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
arXiv Detail & Related papers (2023-07-11T08:51:53Z) - Performance Analysis of Quantum CSS Error-Correcting Codes via
MacWilliams Identities [9.69910104594168]
We analyze the performance of stabilizer codes, one of the most important classes for practical implementations.
We introduce a novel approach that combines the knowledge of WE with a logical operator analysis.
For larger codes our bound provides $rho_mathrmL approx 1215 rho4$ and $rho_mathrmL approx 663 rho5$ for the $[85,1,7]]$ and the $[181,1,10]]$ surface codes.
arXiv Detail & Related papers (2023-05-02T10:19:02Z) - CSS code surgery as a universal construction [51.63482609748332]
We define code maps between Calderbank-Shor-Steane (CSS) codes using maps between chain complexes.
We describe code surgery between such codes using a specific colimit in the category of chain complexes.
arXiv Detail & Related papers (2023-01-31T16:17:25Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches.
We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes.
Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
arXiv Detail & Related papers (2022-10-15T09:22:22Z) - Divisible Codes for Quantum Computation [0.6445605125467572]
Divisible codes are defined by the property that codeword weights share a common divisor greater than one.
This paper explores how they can be used to protect quantum information as it is transformed by logical gates.
arXiv Detail & Related papers (2022-04-27T20:18:51Z) - Distance bounds for generalized bicycle codes [0.7513100214864644]
Generalized bicycle (GB) codes is a class of quantum error-correcting codes constructed from a pair of binary circulant matrices.
We have done an exhaustive enumeration of GB codes for certain prime circulant sizes in a family of two-qubit encoding codes with row weights 4, 6, and 8.
The observed distance scaling is consistent with $A(w)n1/2+B(w)$, where $n$ is the code length and $A(w)$ is increasing with $w$.
arXiv Detail & Related papers (2022-03-31T17:43:34Z) - Partially Concatenated Calderbank-Shor-Steane Codes Achieving the
Quantum Gilbert-Varshamov Bound Asymptotically [36.685393265844986]
We construct new families of quantum error correction codes achieving the quantum-Omega-Varshamov boundally.
$mathscrQ$ can be encoded very efficiently by circuits of size $O(N)$ and depth $O(sqrtN)$.
$mathscrQ$ can also be decoded in parallel in $O(sqrtN)$ time by using $O(sqrtN)$ classical processors.
arXiv Detail & Related papers (2021-07-12T03:27:30Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
We study the setup where each of $n$ users holds an element from a discrete set.
The goal is to count the number of distinct elements across all users.
arXiv Detail & Related papers (2020-09-21T04:13:34Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020)
The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
arXiv Detail & Related papers (2020-02-17T10:53:50Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.