Block Circulant Codes with Application to Decentralized Systems

• URL: http://arxiv.org/abs/2406.12160v2
• Date: Mon, 16 Dec 2024 04:33:04 GMT
• Title: Block Circulant Codes with Application to Decentralized Systems
• Authors: Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau,
• Abstract summary: We develop a family of $[n,k,d]$ block circulant codes that support distributed erasure decoding. The code is ideal for use in protocols that address the data availability problem in blockchain networks.
• Score: 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.

Related papers

• Quantum $(r,δ)$-locally recoverable codes [41.08639347877682]
  A classical $(r,delta)$-locally recoverable code is an error-correcting code such that, for each coordinate $c_i$ of a codeword, there exists a set of at most $r+ delta -1$ coordinates containing $c_i$. These codes are useful for avoiding loss of information in large scale distributed and cloud storage systems.
  arXiv  Detail & Related papers  (2024-12-21T11:45:32Z)
• Characterizing Quantum Codes via the Coefficients in Knill-Laflamme Conditions [3.980076328494117]
  Quantum error correction (QEC) is essential for protecting quantum information against noise. We study the structure of the Knill-Laflamme (KL) coefficients $lambda_ij$ from the condition $PE_idagger E_j P = lambda_ij P$.
  arXiv  Detail & Related papers  (2024-10-10T14:38:15Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques. If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
  arXiv  Detail & Related papers  (2024-06-17T20:54:11Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• $\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)
• 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)
• Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models [59.015960528781115]
  We show how to optimally combine $hatboldsymbol xrm L$ and $hatboldsymbol xrm s$. In order to establish the limiting distribution of $(boldsymbol x, hatboldsymbol xrm L, hatboldsymbol xrm s)$, we design and analyze an Approximate Message Passing (AMP) algorithm.
  arXiv  Detail & Related papers  (2020-08-07T18:20:05Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

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.