Preprints
D. Elimelech, V. Albert, and A. Barg
(2026)
Theory of approximate quantum error correction and the error-set model
submitted
[arXiv]
[abstract]
Abstract:
We develop a theory of approximate quantum error correction (QEC) based on the error-set model, complemented by general methods for code construction. Exact QEC has a powerful error-set structure: by the Knill-Laflamme conditions, a code correcting a given error set automatically protects against every channel whose Kraus operators lie in their linear span. This linearity gives rise to code distance, the equivalence between erasures and general errors, and a theory of asymptotically good codes. A longstanding view has been that these features do not extend to AQEC, leaving the theory essentially channel-by-channel. We show instead that, although full Knill--Laflamme linearity fails, a restricted form survives and suffices to extend all three structural features to the approximate setting. Specifically, a common error-set criterion governs families of channels whose Kraus operators are linear combinations of a given error set and whose coefficient matrices satisfy a spectral constraint. Using the Beny-Oreshkov worst-case and Petz average-case frameworks, we derive uniform fidelity guarantees for these families in terms of two new code parameters--the environment-leakage distance, controlling worst-case performance, and the Knill-Laflamme Hellinger distance, characterizing the average-case performance of Petz recovery.
To demonstrate the scope of this model, we develop partition-based constructions across diverse quantum systems and geometries, placing exact and approximate correction on equal footing. These constructions lead to a metric--error alignment hierarchy for Hilbert spaces, metrics, and error families, which in turn characterizes the resulting recovery guarantees. They yield the first known asymptotically good code families for fermionic systems, one-dimensional Rydberg-blockaded systems, and deletion errors, and extend to other physical platforms.
A. Aydin, A. Barg, and I. Tamo,
(2026)
Breaking the bicycle frame: Coset-based quantum LDPC codes
submitted
[arXiv]
[abstract]
Abstract:
Generalizing the construction of two-block group algebra (2BGA) codes, we introduce a family of two-block quantum LDPC codes constructed using
the action of a group on the cosets of its subgroup. This replaces the regular group actions of the earlier two-block constructions and significantly expands the search space, yielding new quantum LDPC codes outside the 2BGA family. Through a computer search, we identify several new quantum LDPC codes, including weight-6 codes with parameters $[[48,8,6]]$, $[[96,8,10]]$, and $[[224,12,16]]$, as well as weight-8 codes with parameters $[[84,16,8]]$, $[[112,16,10]]$, $[[128,16,12]]$, and $[[168,16,15]]$. Furthermore, we introduce a maximally packed syndrome extraction schedule of depth $w+2$, including initialization and measurement steps, for any code with a maximum stabilizer weight of $w$ from our family. Under a standard circuit-level noise model, our codes, when decoded using BP-OSD, perform competitively with BB codes, achieving thresholds of $\approx0.65\%$ for the weight-6 family and $\approx0.35\%$ for the weight-8 family. Finally, we introduce a group-theoretic framework to generate sequences of graph-based covers of 2BGA codes, recovering and extending recent results on code constructions of this type.
A. Barg, Q.R. Gashi, and T. Xu
(2026)
Minimum distance and decoding of Coxeter codes
submitted
[arXiv]
[abstract]
Abstract:
A binary Coxeter code associated with a finite Coxeter system $(W,S)$ is an ${\mathbb F}_2$-linear span of indicators of standard cosets of a fixed rank. Coxeter codes, introduced in a recent paper by N. Coble and A. Barg, are a generalization of Reed--Muller codes which arise when $W={\mathbb Z}_2^m$ is the Coxeter group of type $mA_1$. In that paper, the authors proposed a conjectural value for the minimum distance of a general Coxeter code. This conjecture is proved in the present work. As a consequence, we obtain a Coxeter-theoretic generalization of Reed's majority-logic decoding algorithm for Reed--Muller codes.
D. Elimelech, A Aydin, and A. Barg
(2026)
Asymptotically good bosonic Fock state codes
submitted
[arXiv]
[abstract]
Abstract:
We study the error-correction properties of multi-mode Fock-state codes under amplitude-damping (AD) noise, focusing on the asymptotic regime in which the total excitation of the code states grows without limit and the number of photon losses induced by the noise scales linearly with it. In this setting, existing code families, which correct only sublinearly many photon losses, do not protect against amplitude-damping (AD) noise with a constant loss parameter. We address this gap by constructing asymptotically good Fock-state codes relying on random classical codes in the discrete simplex. Our approach is based on a new equivalence between approximate correction for the AD channel and exact or approximate correction of sufficiently many photon losses under a truncated AD channel. Unlike many standard constructions of random quantum codes, our construction introduces randomness through the underlying classical indexing structure. Randomization also enables another desirable feature: bounded per-mode occupancy, which limits the number of photons in any individual mode and thereby increases the coherence lifetime of the code states. Finally, via a relation between Fock-state codes and permutation-invariant codes, our results also yield asymptotically good families of qudit permutation-invariant codes as well as codes in monolithic nuclear state spaces.
G. Wang, A. Barg, and N. Kashyap
(2026)
The maximal hard-core model on the triangular lattice
submitted
[arXiv]
[abstract]
Abstract:
We study statistical properties of a model of maximal independent sets on the triangular lattice. As our first result, we show prove phase coexistence in the high-activity regime. For the low-activity case, we characterize extremal periodic Gibbs measures of the model relying on an application of the Pirogov-Sinai theory. We also derive bounds on the capacity of a recoverable system on the lattice associated with the maximal hard-core model.
G. Wang, A. Barg, and N. Kashyap
(2025)
The maximal hard-core model as a recoverable system: Gibbs measures and phase coexistence
submitted
[arXiv]
[abstract]
Abstract:
Recoverable systems provide coarse models of data storage on the two-dimensional square lattice, where each site reconstructs its value from neighboring sites according to a specified local rule. To study the typical behavior of recoverable patterns, this work introduces an interaction potential on the local recovery regions of the lattice, which defines a corresponding interaction model. We establish uniqueness of the Gibbs measure at high temperature and derive bounds on the entropy in the zero- and low-temperature regimes.
For the recovery rule under consideration, exactly recoverable configurations coincide with maximal independent sets of the grid. Relying on methods developed for the standard hard-core model, we show phase coexistence at high activity in the maximal case. Unlike the standard hard-core model, however, the maximal version admits nontrivial ground states even at low activity, and we manage to classify them explicitly. We further verify the Peierls condition for the associated contour model. Combined with the Pirogov-Sinai theory, this shows that each ground state gives rise to an extremal Gibbs measure, proving phase coexistence at low activity. Published/accepted
A. Aydin, V. Albert, and A. Barg
(2026)
Quantum error correction beyond SU(2): spin, permutation-invariant, and bosonic codes from convex geometry
PRX Quantum
vol. 7
010341 (24pp.)
[arXiv]
[doi]
[abstract]
Abstract:
We develop a framework for constructing quantum error-correcting codes and
logical gates for three types of spaces -- composite permutation-invariant
spaces of many qubits or qudits, composite constant-excitation Fock-state
spaces of many bosonic modes, and monolithic nuclear state spaces of atoms,
ions, and molecules. By identifying all three spaces with discrete simplices
and representations of the Lie group $SU(q)$, we prove that many codes and
their gates in $SU(q)$ can be inter-converted between the three state spaces.
We construct new code instances for all three spaces using classical $\ell_1$
codes and Tverberg's theorem, a classic result from convex geometry. We obtain
new families of quantum codes with distance that scales almost linearly with
the code length $N$ by constructing $\ell_1$ codes based on combinatorial
patterns called Sidon sets and utilizing their Tverberg partitions. This
improves upon the existing designs for all the state spaces. We present
explicit constructions of codes with shorter length or lower total
spin/excitation than known codes with similar parameters, new bosonic codes
with exotic Gaussian gates, as well as examples of short codes with distance
larger than the known constructions.
N. Coble and A. Barg
(2026)
Coxeter codes: Extending the Reed--Muller family
Designs, Codes and Cryptography
vol. 94
Article 47
[arXiv]
[doi]
[abstract]
Abstract:
Binary Reed--Muller (RM) codes are defined via evaluations of Boolean-valued functions on ${\mathbb Z}_2^m$. We introduce a class of binary linear codes that generalizes the RM family by replacing the domain ${\mathbb Z}_2^m$ with an arbitrary finite Coxeter group. Like RM codes, this class is closed under duality, forms a nested code sequence, satisfies a multiplication property, and has asymptotic rate determined by a Gaussian distribution. Coxeter codes also give
rise to a family of quantum codes for which transversal diagonal $Z$ rotations can perform non-trivial logic.
M. Pathegama and A. Barg
(2025)
Rényi divergence-based uniformity guarantees for $k$-universal hash functions
IEEE Trans. Inf. Theory
vol. 71
pp. 9203--9214
[arXiv]
[doi]
[abstract]
Abstract:
Universal hash functions map the output of a source to random strings over a finite alphabet, aiming to approximate the uniform distribution on the set of strings. A classic result on these functions, called the Leftover Hash Lemma, gives an estimate of the distance from uniformity based on the assumptions about the min-entropy of the source. We prove several results concerning extensions of this lemma to a class of functions that are $k^\ast$-universal, i.e., $l$-universal for all $2\le l\le k$. As a common distinctive feature, our results provide estimates of closeness to uniformity in terms of the $\alpha$-Rényi divergence for all $\alpha\in (1,\infty]$. For $1\le \alpha\le k$ we show that it is possible to convert all the randomness of the source measured in $\alpha$-Rényi entropy into approximately uniform bits with nearly the same amount of randomness. For large enough $k$ we show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy. We also extend these results to hashing with side information.
A. Barg, N. Coble, D. Hangleiter, and C. Kang
(2026)
Geometric structure and transversal logic of quantum Reed--Muller codes
IEEE Trans. Inf. Theory
vol. 72
pp. 415--436
[arXiv]
[doi]
[abstract]
Abstract:
Designing efficient and noise-tolerant quantum computation protocols generally begins with an understanding of quantum error-correcting codes and their native logical operations. The simplest class of native operations are transversal gates, which are naturally fault-tolerant. In this paper, we aim to characterize the transversal gates of quantum Reed--Muller (RM) codes by exploiting the well-studied properties of their classical counterparts.
We start our work by establishing a new geometric characterization of quantum RM codes via the Boolean hypercube and its associated subcube complex. More specifically, a set of stabilizer generators for a quantum RM code can be described via transversal $X$ and $Z$ operators acting on subcubes of particular dimensions. This characterization leads us to define \emph{subcube operators} composed of single-qubit $\pi/2^k$ $Z$-rotations that act on subcubes of given dimensions. We first characterize the action of subcube operators on the code space: depending on the dimension of the subcube, these operators either (1) act as a logical identity on the code space, (2) implement non-trivial logic, or (3) rotate a state away from the code space. Second, and more remarkably, we uncover that the logic implemented by these operators corresponds to circuits of multi-controlled-$Z$ gates that have an explicit and simple combinatorial description. Overall, this suite of results yields a comprehensive understanding of a class of natural transversal operators for quantum RM codes.
M. Pathegama and A. Barg
(2025)
Limitations of the decoding-to-LPN reduction via code smoothing
Designs, Codes and Cryptograpy
vol. 93
pp. 2761--2778
(Special issue on Code-Based Cryptography)
[arXiv]
[doi]
[abstract]
Abstract:
The Learning Parity with Noise (LPN) problem underlies several classic cryptographic primitives. Researchers have endeavored to demonstrate the algorithmic difficulty of this problem by attempting to find a reduction from the decoding problem of linear codes, for which several hardness results exist. Earlier studies used code smoothing as a technical tool to achieve such reductions, showing that
they are possible for codes with vanishing rate. This has left open the question of attaining a reduction with positive-rate codes. Addressing this case, we characterize the efficiency of the reduction in terms of the parameters of the decoding and LPN problems. As a conclusion, we isolate the parameter regimes for which a meaningful reduction is possible and the regimes for which its existence is unlikely.
M. Pathegama and A. Barg
(2025)
Rényi divergence guarantees for hashing with linear codes
IEEE Trans. Inf. Theory
vol. 71
no. 8
pp. 5809-5819
[arXiv]
[doi]
[abstract]
Abstract:
We consider the problem of distilling uniform random bits from an unknown source with a given $p$-entropy using linear hashing. As our main result, we estimate the expected $p$-divergence from the uniform distribution over the ensemble of random linear codes for all integer $p\ge 2$. The proof relies on analyzing how additive noise, determined by a random element of the code from the ensemble, acts on the source distribution. This action leads to the transformation of the source distribution into an approximately uniform one, a process commonly referred to as distribution smoothing. We also show that hashing with Reed-Muller matrices reaches intrinsic randomness of memoryless Bernoulli sources in the $l_p$ sense for all integer $p\ge 2$.
S. P. Jain, J. T. Iosue, A. Barg, and V. V. Albert
(2024)
Quantum spherical codes
Nature Physics
vol. 20
pp. 1300-1305
[arXiv]
[doi]
[Nature blog]
[phys.org]
[UMD press release]
[abstract]
Abstract:
As with classical computers, quantum computers require error-correction schemes to reliably perform useful large-scale calculations. The nature and frequency of errors depends on the quantum computing platform, and although there is a large literature on qubit-based coding, these are often not directly applicable to devices that store information in bosonic systems such as photonic resonators. Here, we introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, and we obtain multimode extensions of the cat codes that can outperform previous constructions but require a similar type of overhead. Our polytope-based cat codes consist of sets of points with large separation that, at the same time, form averaging sets known as spherical designs. We also recast concatenations of Calderbank–Shor–Steane codes with cat codes as quantum spherical codes, which establishes a method to autonomously protect against dephasing noise.
A. Aydin and A. Barg
(2025)
Class of codes correcting absorptions and emissions
Physical Review A
vol. 111
Paper no. 022415
[arXiv]
[doi]
[abstract]
Abstract:
We construct a general family of quantum codes that protect against all emission, absorption, dephasing, and raising/lowering errors up to an arbitrary fixed order. Such codes are known in the literature as absorption-emission (AE) codes. We derive simplified error correction conditions for a general AE code and show that any permutation-invariant code that corrects $\le t$ errors can be mapped to an AE code that corrects up to order-$t$ transitions. Carefully tuning the parameters of permutationally invariant codes, we
construct several examples of efficient AE codes, hosted in systems with low total angular momentum.
Our results also imply that spin codes can be mapped to AE codes, enabling us to characterize logical operators for certain subclasses of such codes.
A. Patra and A. Barg
(2025)
Targeted Clifford logical gates for hypergraph product codes
Quantum
vol. 9
1842
[arXiv]
[doi]
[abstract]
Abstract:
Starting with an explicit framework for designing logical Clifford circuits for CSS codes, we construct logical gates for Hypergraph Product Codes. We first derive symplectic matrices for CNOT, CZ, Phase, and Hadamard operators, which together generate the Clifford group. This enables us to design explicit transformations that result in targeted logical gates for arbitrary codes in this family. As a concrete example, we give logical circuits for the $[[18,2,3]]$ toric code.
A. Patra and A. Barg
(2025)
Generalized regenerating codes and node repair on graphs
IEEE Trans. Inf. Theory
vol. 71
pp. 1613--1630
[arXiv]
[doi]
[abstract]
Abstract:
We continue our study of regenerating codes in distributed storage systems where connections between the nodes are constrained by a graph. In this problem, the failed node downloads the information stored at a subset of vertices of the graph for the purpose of recovering the lost data. This information is moved across the network, and the cost of node repair is determined by the graphical distance from the helper nodes to the failed node. This problem was formulated in our recent work (IEEE IT Transactions, May 2022) where we showed that processing of the information at the intermediate nodes can yield savings in repair bandwidth over the direct forwarding of the data.
While the previous paper was limited to the MSR case, here we extend our study to the case of general regenerating codes. We derive a lower bound on the repair bandwidth and formulate repair procedures with intermediate processing for several families of regenerating codes, with an emphasis on the recent constructions from multilinear algebra. We also consider the task of data retrieval for codes on graphs, deriving a lower bound on the communication bandwidth and showing that it can be attained at the MBR point of the storage-bandwidth tradeoff curve.
A. Barg, O. Elishco, R. Gabrys, G. Wang, and E. Yaakobi
(2024)
Storage codes and recoverable systems on lines and grids
Designs, Codes and Cryptography
vol. 92
pp. 4145--4168
[arXiv]
[doi]
[abstract]
Abstract:
A storage code is an assignment of symbols to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors, or more generally, of a certain neighborhood of the vertex in $G$. In this work we introduce a new construction method of storage codes, enabling one to construct new codes from known ones via an interleaving procedure driven by resolvable designs. We also study storage codes on $\mathbb{Z}$ and $\mathbb{Z}^2$ (lines and grids), finding closed-form expressions for the capacity of several one and two-dimensional systems depending on their recovery set, using connections between storage codes, graphs, anticodes, and difference-avoiding sets.
A. Barg, M. Schwartz, and L. Yohananov
(2024)
Storage codes on coset graphs with asymptotically unit rate
Combinatorica
vol. 44
1193--1209
[arXiv]
[doi]
[abstract]
Abstract:
A storage code on a graph G is a set of assignments of symbols to the vertices such that every vertex can recover its value by looking at its neighbors. We consider the question of constructing large-size storage codes on triangle-free graphs constructed as coset graphs of binary linear codes. Previously it was shown that there are infinite families of binary storage codes on coset graphs with rate converging to 3/4. Here we show that codes on such graphs can attain rate asymptotically approaching 1. Equivalently, this question can be phrased as a version of hat-guessing games on graphs (e.g., P.J. Cameron e.a., Electronic J. Comb. 2016). In this language, we construct triangle-free graphs with success probability of the players approaching one as the number of vertices tends to infinity. Furthermore, finding linear index codes of rate approaching zero is also an equivalent problem.
A. Barg, A, Glazyrin, W.-J. Kao, C.-Y. Lai, P.-C. Tseng, and W.-H. Yu
(2024)
The size of optimal binary codes with 2, 3, and 4 distances
Combinatorial Theory
vol. 4
#4
[arXiv]
[doi]
[abstract]
Abstract:
We address the maximum size of binary codes and binary constant weight codes with few distances. Previous works established a number of bounds for these quantities as well as the exact values for a range of small code lengths. As our main results, we determine the exact size of maximal binary codes with two distances for all lengths $n\ge 6$ as well as the exact size of maximal binary constant weight codes with 2,3, and 4 distances for several values of the weight and for all but small lengths.
A. Aydin, M. Alekseyev, and A. Barg
(2024)
A family of permutationally invariant quantum codes
Quantum
vol. 8
1321
[arXiv]
[doi]
[Perspective by Yingkai Ouyang]
[abstract]
Abstract:
We construct a new family of permutationally invariant codes that correct $t$ Pauli errors for any $t\ge 1$. We also show that codes in the new family correct quantum deletion errors as well as spontaneous decay errors. Our construction contains some of the previously known permutationally invariant quantum codes as particular cases, which also admit transversal gates. In many cases, the codes in the new family are shorter than the best previously known explicit permutationally invariant codes for Pauli errors and deletions. Furthermore, our new code family includes a new $((4,2,2))$ optimal single-deletion-correcting code. As a separate result, we generalize the conditions for permutationally invariant codes to correct $t$ Pauli errors from the previously known results for $t=1$ to any number of errors. For small $t$, these conditions can be used to construct new examples of codes by computer.s for $t=1$ to any number of errors. For small $t$, these conditions can be used to construct new examples of codes by computer.
M. Pathegama and A. Barg
(2023)
Smoothing of binary codes, uniform distributions and applications
Entropy
vol. 25
Art. 1515
[arXiv]
[doi]
[abstract]
Abstract:
The action of a noise operator on a code transforms it into a distribution on the respective space. Some common examples from information theory include Bernoulli noise acting on a code in the Hamming space and Gaussian noise acting on a lattice in the Euclidean space. We aim to characterize the cases when the output distribution is close to the uniform distribution on the space, as measured by R{\'e}nyi divergence of order $\alpha \in (1,\infty]$. A version of this question is known as the channel resolvability problem in information theory, and it has implications for security guarantees in wiretap channels, error correction, discrepancy, worst-to-average case complexity reductions, and many other problems.
Our work quantifies the requirements for asymptotic uniformity (perfect smoothing) and identifies explicit code families that achieve it under the action of the Bernoulli and ball noise operators on the code. We derive expressions for the minimum rate of codes required to attain
asymptotically perfect smoothing. In proving our results, we leverage recent results from harmonic analysis of functions on the Hamming space. Another result pertains to the use of code families in Wyner's transmission scheme on the binary wiretap channel. We identify explicit families that guarantee strong secrecy when applied in this scheme, showing that nested Reed-Muller codes can transmit messages reliably and securely over a binary symmetric wiretap channel with a positive rate. Finally, we establish a connection between smoothing and error correction in the binary symmetric channel.
A. Barg, P. Boyvalenkov, and M. Stoyanova
(2023)
Bounds for the sum of distances of spherical sets of small size
Discrete Mathematics
vol. 346
Art. 113346
[arXiv]
[doi]
[abstract]
Abstract:
We derive upper and lower bounds on the sum of distances of a spherical code of size $N$ in $n$ dimensions when
$N\sim n^\alpha, 0<\alpha\le 2.$ The bounds are derived by specializing recent general, universal bounds on
energy of spherical sets. We discuss asymptotic behavior of our bounds along with several examples of codes
whose sum of distances closely follows the upper bound.
A. Barg and G. Zémor
(2022)
High-rate storage codes on triangle-free graphs
IEEE Transactions on Information Theory
vol. 68
pp. 7787-7797
[arXiv]
[doi]
[abstract]
Abstract:
Consider an assignment of bits to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length $|V|$ on $G$. The storage code problem can be equivalently formulated as maximizing the probability of success in a guessing game on graphs, or constructing index codes of small rate.
If $G$ contains many cliques, it is easy to construct codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where constructing codes of rate $>1/2$ is a nontrivial task, with few known results. In this work we construct infinite families of linear storage codes with high rate relying on coset graphs of binary linear codes. We also derive necessary conditions for such codes to have high rate, and even rate potentially close to one.
We also address correction of multiple erasures in the codeword, deriving recovery guarantees based on expansion properties of the graph.
Finally, we point out connections between linear storage codes and quantum CSS codes, a link to bootstrap percolation and contagion spread in graphs, and formulate a number of open problems.
O Elishco, A. Barg
(2022)
Recoverable systems
IEEE Transactions on Information Theory
vol. 68
pp. 3681-3699
[arXiv]
[doi]
[abstract]
Abstract: Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every $k$-tuple of consecutive entries is uniquely recoverable from its $l$-neighborhood in the sequence. We address the problem of finding the maximum growth rate of the set, which we term capacity, as well as constructions of explicit families that approach the optimal rate. The techniques that we employ rely on the connection of this problem with constrained systems.
In the second part of the paper we consider a modification of the problem wherein the entries in the sequence are viewed as random variables over a finite alphabet that follow some joint distribution, and the recovery condition requires that the Shannon entropy of the $k$-tuple conditioned on its $l$-neighborhood be bounded above by some $\epsilon>0.$ We study properties of measures on infinite sequences that maximize the metric entropy under the recoverability condition. Drawing on tools from ergodic theory, we prove some properties of entropy-maximizing measures. We also suggest a procedure of constructing an $\epsilon$-recoverable measure from a corresponding deterministic system, and prove that for small $\epsilon$ the constructed measure is a maximizer of the metric entropy.
[talk]
A. Patra and A. Barg
(2022)
Node repair on connected graphs
IEEE Transactions on Information Theory
vol. 68
pp. 3081-3095
[arXiv]
[doi]
[abstract]
Abstract:
We study the problem of erasure correction (node repair) for regenerating codes defined on graphs wherein the cost of transmitting the information to the failed node depends on the graphical distance from this node to the helper vertices of the graph. The information passed to the failed node from the helpers traverses several vertices of the graph, and savings in communication complexity can be attained if the intermediate vertices process the information rather than simply relaying it toward the failed node. We derive simple information-theoretic bounds on the amount of information communicated between the nodes in the course of the repair. Next we show that Minimum Storage Regenerating (MSR) codes can be modified to perform the intermediate processing, thereby attaining the lower bound on the information exchange on the graph. We also consider node repair when the underlying graph is random, deriving conditions on the parameters that support recovery of the failed node with communication complexity smaller than required by the simple relaying.
A. Barg, Z. Chen, and I. Tamo
(2022)
A construction of maximally recoverable codes
Designs, Codes and Cryptography
vol. 90
pp. 939-945
[arXiv]
[doi]
[abstract]
Abstract:
We construct a family of linear maximally recoverable codes with locality $r$ and dimension $r+1.$ For codes of length $n$ with $r\approx n^\alpha, 0\le\alpha\le 1$ the code alphabet is of the order $n^{1+3\alpha},$ which improves upon the previously known constructions of maximally recoverable
codes.
A. Barg and M.M. Skriganov
(2021)
Bounds for discrepancies in the Hamming space
Journal of Complexity
vol. 65
Art. 101552
[arXiv]
[doi]
[abstract]
Abstract:
We derive bounds for the ball $L_p$-discrepancies in the Hamming space for
$0 < p < \infty$ and $p=\infty$. Sharp estimates of discrepancies have been
obtained for many spaces such as the Euclidean spheres and more general compact
Riemannian manifolds. In the present paper, we show that the
behavior of discrepancies in the Hamming space differs fundamentally because
the volume of the ball in this space depends on its radius exponentially while
such a dependence for the Riemannian manifolds is polynomial.
A. Barg
(2021)
Stolarsky's invariance principle for finite metric spaces
Mathematika
vol. 67
pp. 158-186
[arXiv]
[doi]
[abstract]
Abstract:
Stolarsky's invariance principle quantifies the deviation of a subset of a metric space from the uniform distribution. Classically derived for spherical sets, it has been recently studied in a number of other situations, revealing a general structure behind various forms of the main identity. In this work we consider the case of finite metric spaces, relating the quadratic discrepancy of a subset to a certain function of the distribution of distances in it. Our main results are related to a concrete form of the invariance principle for the Hamming space. We derive several equivalent versions of the expression for the discrepancy of a code, including expansions of the discrepancy and associated kernels in the Krawtchouk basis. Codes that have the smallest possible quadratic discrepancy among all subsets of the same cardinality can be naturally viewed as energy minimizing subsets in the space. Using linear programming, we find several bounds on the minimal discrepancy and give examples of minimizing configurations. In particular, we show that all binary perfect codes have the smallest possible discrepancy.
[slides]
[Notes]
Details are available here.
O. Elishco and A. Barg
(2021)
Capacity of dynamical distributed storage
IEEE Trans. Inform. Theory
vol. 67, no.1
pp. 329-346
[arXiv]
[doi]
[abstract]
Abstract:
We introduce a dynamical model of node repair in distributed storage systems wherein the storage nodes are subjected to failures according
to independent Poisson processes. The main parameter that we study is the time-average capacity of the network in the scenario where a
fixed subset of the nodes support a higher repair bandwidth than the other nodes. The sequence of node failures generates random permutations
of the nodes in the encoded block, and we model the state of the network as a Markov random walk on permutations of $n$ elements.
As our main result we show that the capacity of the network can be increased compared to the static (worst-case) model of the storage
system, while maintainingthe same (average) repair bandwidth, and we derive estimates of the increase.
We also quantify the capacity increase in the case that the repair center has information about the sequence of the recently failed
storage nodes.
Z. Chen and A. Barg
(2021)
Cyclic and convolutional codes with locality
IEEE Trans. Inform. Theory
vol. 67, no. 2
pp. 755-769
[arXiv]
[doi]
[abstract]
Abstract:
Locally recoverable (LRC) codes and their variants have been extensively studied in recent years. In this paper we focus on cyclic constructions
of LRC codes and derive conditions on the zeros of the code that support the property of hierarchical locality. As a result, we obtain
a general family of hierarchical LRC codes for a new range of code parameters. We also observe that our approach enables one to represent
an LRC code in quasicyclic form, and use this representation to construct tail-biting convolutional LRC codes with locality.
Among other results, we extend the general approach to cyclic codes with locality to multidimensional cyclic codes, yielding new families of LRC
codes with availability, and construct a family of $q$-ary cyclic hierarchical LRC codes of unbounded length.
Z. Chen, Min Ye, and A. Barg
(2020)
Enabling error correction and optimal access for the repair of Reed-Solomon codes
IEEE Trans. Inform. Theory
vol. 66, no. 12
pp. 7439--7456
M. Ye, I. Tamo, and A. Barg
(2020)
Error correction based on partial information
IEEE Trans. Inform. Theory
vol. 66, no. 3
pp. 1396-1404
Z. Chan and A. Barg
(2020)
Explicit constructions of MSR codes for clustered distributed storage: The rack-aware storage
model
IEEE Trans. Inform. Theory
vol. 66, no. 2
pp. 866-899
O. Kolosov, G. Yadgar, M. Liram, I.Tamo, and A. Barg
(2020)
On fault tolerance, locality, and optimality in locally repairable codes
ACM Trans. Storage
vol. 16, no. 2
Article 11, 35pp.
[doi]
[abstract]
Abstract:
Erasure codes in large-scale storage systems allow recovery of data from a failed node. A recently developed class of codes, locally repairable codes (LRCs), offers tradeoffs between storage overhead and repair cost. LRCs facilitate efficient recovery scenarios by adding parity blocks to the system. However, these additional blocks may eventually increase the number of blocks that must be reconstructed. Existing LRCs differ in their use of the parity blocks, in their locality semantics, and in their parameter space. Thus, existing theoretical models cannot directly compare different LRCs to determine which code offers the best recovery performance, and at what cost.
We perform the first systematic comparison of existing LRC approaches. We analyze Xorbas, Azure’s LRCs, and Optimal-LRCs in light of two new metrics: average degraded read cost and normalized repair cost. We show the tradeoff between these costs and the code’s fault tolerance, and that different approaches offer different choices in this tradeoff. Our experimental evaluation on a Ceph cluster further demonstrates the different effects of realistic system bottlenecks on the benefit from each LRC approach. Despite these differences, the normalized repair cost metric can reliably identify the LRC approach that would achieve the lowest repair cost in each setup.
M. Ye and A. Barg
(2019)
Optimal locally private estimation under $\ell_p$ loss for $1\le p\le 2$
The Electronic Journal of Statistics
vol. 13, no. 2
pp. 4102-4120
S. Ballentine, A. Barg, and S. Vlăduţ
(2019)
Codes with hierarchical locality from covering maps of curves
IEEE Trans. Inform. Theory
vol. 65, no. 10
pp. 6056--6071
[arXiv]
[doi]
[abstract]
Abstract:
Locally recoverable (LRC) codes provide ways of recovering erased coordinates of the codeword without having to access each of the remaining coordinates. A subfamily of LRC codes with hierarchical locality (H-LRC codes) provides added flexibility to the construction by introducing several tiers of recoverability for correcting different numbers of erasures. We present a general construction of codes with 2-level hierarchical locality from maps between algebraic curves and specialize it to several code families obtained from quotients of curves by a subgroup of the automorphism group, including rational, elliptic, Kummer, and Artin-Schreier curves. We further address the question of H-LRC codes with availability, and suggest a general construction of such codes from fiber products of curves. Detailed calculations of parameters for H-LRC codes with availability are performed for Reed-Solomon- and Hermitian-like code families. Finally, we construct asymptotically good families of H-LRC codes from curves related to the Garcia-Stichtenoth tower.
M. Ye, I. Tamo, and A. Barg
(2019)
The repair problem for Reed–Solomon codes: Optimal repair of single and multiple erasures with almost optimal node size
IEEE Trans. Inform. Theory
vol. 65, no. 5
pp. 2673-2695
[arXiv1]
[arXiv2]
[doi]
[abstract]
Abstract:
The repair problem in distributed storage addresses recovery of the data encoded using an erasure code, for instance, a Reed-Solomon (RS) code. We consider the problem of repairing a single node or multiple nodes in RS-coded storage systems using the smallest possible amount of inter-nodal communication. According to the cut-set bound, communication cost of repairing $h\ge 1$ failed nodes for an $(n,k=n-r)$ MDS code using $d$ helper nodes is at least $dhl/(d+h-k),$ where $l$ is the size of the node. Guruswami and Wootters (2016) initiated the study of efficient repair of RS codes, showing that they can be repaired using a smaller bandwidth than under the trivial approach. At the same time, their work as well as follow-up papers stopped short of constructing RS codes (or any scalar MDS codes) that meet the cut-set bound with equality.
[FOCS extended abstract]
In this paper we construct families of RS codes that achieve the cutset bound for repair of one or several nodes. In the single-node case, we present RS codes of length $n$ over the field ${\mathbb F}_{q^l}, l=\exp((1+o(1))n\log n)$ that meet the cut-set bound. We also prove an almost matching lower bound on $l$, showing that super-exponential scaling is both necessary and sufficient for scalar MDS codes to achieve the cut-set bound using linear repair schemes. For the case of multiple nodes, we construct a family of RS codes that achieve the cut-set bound universally for the repair of any $h=1,2,\dots,r$ failed nodes from any subset of $d$ helper nodes, $k\le d\le n-h.$ For a fixed number of parities $r$ the node size of the constructed codes is close to the smallest possible node size for codes with such properties.
M. Ye and A. Barg
(2019)
Cooperative repair: Constructions of optimal MDS codes for all admissible parameters
IEEE Trans. Inform. Theory
vol. 65, no. 3
pp. 1639--1656
M. Ye and A. Barg
(2018)
Optimal schemes for discrete distribution estimation under locally differential privacy
IEEE Trans. Inform. Theory
vol. 64, no. 5
pp. 2673--2695
M. N. Krishnan, B. Puranik, P.V. Kumar, I. Tamo, A. Barg
(2018)
Exploiting locality for improved decoding of binary cyclic codes
IEEE Transactions on Communications
vol. 66, no. 6
pp. 2346-2358
A. Agarwal, A. Barg, S. Hu, A. Mazumdar, I. Tamo
(2018)
Combinatorial alphabet-dependent bounds for locally recoverable codes
IEEE Trans. Inform. Theory
vol. 64, no. 5
pp. 3481-3492
T.C. Gulcu, Min Ye, and A. Barg
(2018)
Construction of polar codes for arbitrary discrete memoryless
channels
IEEE Trans. Inform. Theory
vol. 64, no. 1
pp. 309-321
A. Barg, K. Haymaker, E. Howe, G. Matthews, and A. Várilly-Alvarado
(2017)
Locally recoverable codes from algebraic curves and surfaces
Algebraic Geometry for Coding Theory and Cryptography
Springer
pp. 95-126
A. Barg and A. Mazumdar
(2017)
Group testing schemes from codes and designs
IEEE Trans. Inform. Theory
vol. 63, no. 11
pp. 7131-7141
M. Ye and A. Barg
(2017)
Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization
IEEE Trans. Inform. Theory
vol. 63, no. 10
pp. 6307-6317
A. Barg, I. Tamo, and S. Vlăduţ
(2017)
Locally recoverable codes on algebraic curves
IEEE Trans. Inform. Theory
vol. 63, no. 8
pp. 4928-4939
M. Ye and A. Barg
(2017)
Explicit constructions of high-rate MDS array codes with optimal repair bandwidth
IEEE Trans. Inform. Theory
vol. 63, no. 4
pp. 2001-2014
T.C. Gulcu and A. Barg
(2017)
Achieving secrecy capacity of the general wiretap channel and broadcast channel
with a confidential component
IEEE Trans. Inform. Theory
vol. 63, no. 1
pp. 1311-1324
I. Tamo, A. Barg, S. Goparaju and R. Calderbank
(2016)
Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes
International Journal of Information and Coding Theory
vol. 3, no. 4
pp. 345-364
I. Tamo, A. Barg, and A. Frolov
(2016)
Bounds for locally recoverable codes
IEEE Trans. Inf. Theory
vol. 62, no. 6
pp. 3070-3083
T.C. Gulcu and A. Barg
(2016)
Interactive function computation via polar coding
Probl. Inform. Trans.
vol. 52, no. 1
pp. 66-91
A. Barg and W. Park
(2015)
On linear ordered codes
Moscow Mathematical Journal
vol. 15, no. 4
pp. 679-702 (earlier version 2010 Allerton conference)
[arXiv]
[doi]
[abstract]
Abstract:
We consider linear codes in the metric space with the Niederreiter–Rosenbloom–Tsfasman (NRT) metric, calling them linear ordered codes. In the first part of the paper we examine a linear-algebraic perspective of linear ordered codes, focusing on the distribution of “shapes” of codevectors. We define a multivariate Tutte polynomial of the linear code and prove a duality relation for the Tutte polynomial of the code and its dual code. We further relate the Tutte polynomial to the distribution of support shapes of linear ordered codes, and find this distribution for ordered MDS codes. Using these results as a motivation, we consider ordered matroids defined for the NRT poset and establish basic properties of their Tutte polynomials. We also discuss connections of linear ordered codes with simple models of information transmission channels.
A. Barg and I. Tamo
(2015)
On codes with the locality property
IEEE Inf. Theory Society Newsletter
no.4 [pdf]
A. Barg, A. Mazumdar, and R. Wang
(2015)
Restricted isometry property of random subdictionaries
IEEE Trans. Inf. Theory
vol. 61, no. 8
pp. 4440-4450
[arXiv]
[doi]
[abstract]
Abstract:
We study statistical restricted isometry, a property closely related to sparse signal recovery,
of deterministic sensing matrices of size $m \times N$. A matrix is said to have a statistical
restricted isometry property (StRIP) of order $k$ if most submatrices with $k$ columns define a near-isometric map
of ${\mathbb R}^k$ into ${\mathbb R}^m$.
As our main result, we establish sufficient conditions for the
StRIP property of a matrix in terms of the mutual coherence and \red{mean square coherence.} We show that for many existing deterministic families of sampling matrices,
$m=O(k)$ rows suffice for $k$-StRIP, which is an improvement over the known estimates of either $m = \Theta(k \log N)$ or $m = \Theta(k\log k)$.
A. Barg and M.M. Skriganov
(2015)
Association schemes on general measure spaces and zero-dimensional Abelian groups
Advances in Mathematics
vol. 281, no. 8
pp. 142-247
[arXiv]
[doi]
[abstract]
Abstract:
Association schemes form one of the main objects of algebraic
combinatorics, classically defined on finite sets. At the same time, direct extensions of this concept to infinite sets encounter
some problems even in the case of countable sets, for instance, countable discrete Abelian groups.
In an attempt to resolve these difficulties, we define association schemes on arbitrary, possibly uncountable sets
with a measure. We study operator realizations of the adjacency algebras of schemes and derive simple properties of
these algebras. However, constructing a complete theory in the general case faces a set of obstacles related to the properties
of the adjacency algebras and associated projection operators.
To develop a theory of association schemes, we focus on schemes on topological Abelian groups where we can employ duality theory
and the machinery of harmonic analysis. Using the language of spectrally dual partitions, we prove that such groups support
the construction of general Abelian (translation) schemes and establish properties of their spectral parameters (eigenvalues).
Addressing the existence question of spectrally dual partitions, we show that they arise naturally on topological zero-dimensional Abelian groups, for instance, Cantor-type groups or the groups of $p$-adic numbers. This enables us to construct large classes of examples of dual pairs of association schemes on zero-dimensional groups with respect to their Haar measure, and to compute their eigenvalues and intersection numbers (structural constants). We also derive properties of infinite metric schemes, connecting them with the properties of the non-Archimedean metric on the group. Next we focus on the connection between schemes on zero-dimensional groups and harmonic analysis. We show that the eigenvalues have a natural interpretation in terms of Littlewood-Paley wavelet bases, and in the (equivalent) language of martingale theory. For a class of nonmetric schemes constructed in the paper, the eigenvalues coincide with values of orthogonal function systems on zero-dimensional groups. We observe that these functions, which we call Haar-like bases, have the properties of wavelet bases on the group, including in some special cases the self-similarity property. This establishes a seemingly new link between algebraic combinatorics and (non-Archimedean) harmonic analysis. We conclude the paper by studying some analogs of problems of classical coding theory related to the theory of association schemes.
A. Barg, A. Glazyrin, K. Okoudjou and W.-H. Yu
(2015)
Finite two-distance tight frames
Linear Algebra Appl.
vol. 475
pp. 163-175
M. Ye and A. Barg
(2015)
Polar codes for distributed hierarchical source coding
Advances in Mathematics of Communication
vol. 9, no. 1
pp. 87-103
M. Ye and A. Barg
(2014)
Universal source polarization and an application to a multi-user
problem
Proc. 2014 Allerton conference
pp. 805-812
A. Barg and W.-H. Yu
(2014)
New bounds for equiangular lines
Discrete Geometry and Algebraic Combinatorics, A. Barg and O. Musin,
Editors, AMS Series: Contemporary Mathematics
vol. 625
pp. 111-121
I. Tamo and A. Barg
(2014)
A family of optimal locally recoverable codes
IEEE Trans. Inf. Theory
vol. 62, no. 8
pp. 4661-4676
[arXiv]
[doi]
[addendum]
[abstract]
Abstract:
A code over a finite alphabet is called locally recoverable (LRC) if every symbol in the encoding is a function of a small number (at most $r$ ) other symbols. We present a family of LRC codes that attain the maximum possible value of the distance for a given locality parameter and code cardinality. The codewords are obtained as evaluations of specially constructed polynomials over a finite field, and reduce to a Reed-Solomon code if the locality parameter $r$ is set to be equal to the code dimension. The size of the code alphabet for most parameters is only slightly greater than the code length. The recovery procedure is performed by polynomial interpolation over r points. We also construct codes with several disjoint recovering sets for every symbol. This construction enables the system to conduct several independent and simultaneous recovery processes of a specific symbol by accessing different parts of the codeword. This property enables high availability of frequently accessed data.
The construction assumes that $(r+1)|n$. In an addendum written in 2018 we removed this restriction.
A. Barg, L. Felix, M. Firer, and M. Spreafico
(2014)
Linear codes on posets with extension property
Discrete Mathematics
vol. 317
pp. 4661-4676
[arXiv]
[doi]
[abstract]
Abstract:
We investigate linear and additive codes in partially ordered Hamming-like spaces that satisfy the extension property, meaning that automorphisms of ideals extend to automorphisms of the poset. The codes are naturally described in terms of translation association schemes that originate from the groups of linear isometries of the space. We address questions of duality and invariants of codes, establishing a connection between the dual association scheme and the scheme defined on the dual poset (they are isomorphic if and only if the poset is self-dual). We further discuss invariants that play the role of weight enumerators of codes in the poset case. In the case of regular rooted trees such invariants are linked to the classical problem of tree isomorphism. We also study the question of whether these invariants are preserved under standard operations on posets such as the ordinal sum and the like.
A. Barg and W.-H. Yu
(2013)
New bounds for spherical two-distance sets
Experimental Mathematics
vol. 22
pp. 187-194
[arXiv]
[doi]
[abstract]
Abstract:
A spherical two-distance set is a finite collection of unit vectors in ${\mathbb R}^n$ such that the distance between two distinct vectors assumes one of only two values. We use the semidefinite programming method to compute improved estimates of the maximum size of spherical two-distance sets. Exact answers are found for dimensions $n=23$ and $40\le n\le 93 (n\ne 46, 78),$ where previous results gave divergent bounds.
A. Barg and G. Kabatiansky
(2013)
Robust parent identifying codes and combinatorial arrays
IEEE Trans. Inf. Theory
vol. 59, no. 2
pp. 994-1003
A. Mazumdar, A. Barg and G. Zémor
(2013)
Constructions of rank modulation codes
IEEE Trans. Inf. Theory
vol. 59, no. 2
pp. 1018-1029
W. Park and A. Barg
(2013)
Polar codes for $q$-ary channels, $q=2^r$
IEEE Trans. Inf. Theory
vol. 59, no. 2
pp. 955-969
A. Mazumdar, A. Barg, and N. Kashyap
(2011)
Coding for high-density recording on a 1-D granular magnetic medium
IEEE Trans. Inf. Theory
vol. 57, no. 11
pp. 7403-7417
A. Mazumdar and A. Barg
(2011)
On the number of errors correctable with codes on graphs
IEEE Trans. Inf. Theory
vol. 57, no. 2
pp. 910--919
A. Barg and O. Musin
(2011)
Bounds on sets with few distances
Journal of Combinatorial Theory Ser. A
vol. 118, no. 4
pp. 1465-1474
A. Barg and G. Zémor
(2011)
List decoding of product codes by the MinSum algorithm (draft)
Proc 2011 IEEE ISIT
pp. 1273-1277
[doi]
[abstract]
Abstract:
We introduce a MinSum-based list decoder for product codes and analyze its performance. We show that it can guarantee successful list decoding for decoding radii that lie above half the code's minimum distance.
N.P. Anthapadmanabhan and A. Barg
(2011)
Two-level fingerprinting codes: A stronger definition and
constructions (draft)
Proc. 2011 IEEE ISIT
pp. 2528-2532
[pdf]
[doi]
[abstract]
Abstract:
We develop the concept of hierarchical fingerprinting introduced in our
recent work ([arxiv], ISIT2009).
The object of two-level fingerprinting is content protection
against coalitions of $t$ pirates in such a manner that one of the pirates
can be identified exactly if $t\le t_2$ or localized to within a small
group if $t_2 < t \le t_1,$ where $t_1$ and $t_2$ are parameters of the system.
In this work, we require the additional property that in the latter case no innocent
users are accused of belonging to the pirate coalition.
We construct two-level fingerprinting codes with polynomial
complexity of identification that satisfy the strong definition
of hierarchical fingerprinting described above.
A. Barg and A. Mazumdar
(2011)
Codes in permutations and error correction for rank modulation
IEEE Trans. Inf. Theory
56
pp. 3158 - 3165
[arXiv]
[doi]
[abstract]
Abstract:
Codes for rank modulation have been recently proposed as a means of protecting flash memory devices from errors. We study basic coding theoretic problems for such codes, representing them as subsets of the set of permutations of $n$ elements equipped with the Kendall tau distance. We derive several lower and upper bounds on the size of codes. These bounds enable us to establish the exact scaling of the size of optimal codes for large values of $n$. We also show the existence of codes whose size is within a constant factor of the sphere packing bound for any fixed number of errors.
S. Nitinawarat, C. Ye, A. Barg, P. Narayan, A. Reznik
(2010)
Secret key generation for a pairwise independent network
IEEE Trans. Inf. Theory
vol. 56, no. 12
pp. 6482--6489
[pdf]
[doi]
[abstract]
Abstract:
We consider secret key generation for a “pairwise independent
network” model in which every pair of terminals observes
correlated sources that are independent of sources observed
by all other pairs of terminals. The terminals are then allowed to
communicate publicly with all such communication being observed
by all the terminals. The objective is to generate a secret key shared
by a given subset of terminals at the largest rate possible, with
the cooperation of any remaining terminals. Secrecy is required
from an eavesdropper that has access to the public interterminal
communication. A (single-letter) formula for secret key capacity
brings out a natural connection between the problem of secret key
generation and a combinatorial problem of maximal packing of
Steiner trees in an associated multigraph. An explicit algorithm is
proposed for secret key generation based on a maximal packing of
Steiner trees in a multigraph; the corresponding maximum rate of
Steiner tree packing is thus a lower bound for the secret key capacity.
When only two of the terminals or when all the terminals
seek to share a secret key, the mentioned algorithm achieves secret
key capacity in which case the bound is tight.
A. Barg and P. Purkayastha
(2009)
Near-MDS poset codes and distributions
Error-Correcting Codes, Finite Geometries, and Cryptography
A. Bruen and D. Wehlau, Editors, AMS Series: Contemporary Mathematics vol.
523
pp. 135-147
A. Barg and P. Purkayastha
(2009)
Bounds on ordered codes and orthogonal arrays
Moscow Mathematical Journal
vol. 9, no. 2
pp. 211-243
[arXiv]
[doi]
[abstract]
Abstract:
We derive new estimates of the size of codes and orthogonal
arrays in the ordered Hamming space (the Niederreiter-Rosenbloom-Tsfasman space).
We also show that the eigenvalues of the ordered
Hamming scheme, the association scheme that describes the combinatorics of the space,
are given by the multivariate Krawtchouk polynomials, and establish some of their properties.
A. Barg, A. Mazumdar, and G. Zémor
(2008)
Weight distribution and decoding of codes on hypergraphs
Advances in Math. of Communication
vol. 2, no. 4
pp. 433-450
A. Barg and A. Duggan
(2008)
Performance analysis of soft decision decoding of Reed Solomon codes
IEEE Trans. Inform. Theory
vol. 54
pp. 433-450
N.P. Anthapadmanabhan, A. Barg, and I. Dumer
(2008)
On the fingerprinting capacity under the marking assumption
IEEE Trans. Inf. Theory
vol. 54, no.6
pp. 2678-2689
A. Barg and D. Nogin
(2008)
A functional view of upper bounds on codes
in book "Coding and Cryptology," edited by Y. Li et al., World
Scientific
pp. 15-24
A. Barg and O. Musin
(2007)
Codes in spherical caps
Advances in Math. of Communications
vol. 1, no.1
pp. 131-149
A. Barg and D. Nogin
(2006)
Spectral approach to linear programming bounds on codes
Problems of Information Transmission
vol. 42, no.2
pp. 77-89
[arXiv]
[doi]
[abstract]
Abstract:
We give new proofs of asymptotic upper bounds
of coding theory obtained within the frame of Delsarte's linear programming
method. The proofs rely on the analysis of eigenvectors of some
finite-dimensional operators related to orthogonal polynomials. The examples
of the method considered in the paper include binary codes, binary
constant-weight codes, spherical codes, and codes in the projective spaces.
A. Barg and D. Nogin
(2006)
A bound on Grassmannian codes
Journal of Combinatorial Theory Ser. A
vol. 113, no. 8
pp. 1629-1635
A. Barg and G. Zémor
(2006)
Distance properties of expander codes
IEEE Trans. Inf. Theory
vol. 52, no.1
pp. 78-90
A. Barg and G. Zémor
(2005)
Multilevel expander codes
In "Algebraic Coding Theory and Information Theory"
AMS-DIMACS series, vol. 68
pp. 69-83
A. Barg and A. McGregor
(2005)
Distance distribution of binary codes and the error probability of decoding
IEEE Trans. Inf. Theory
vol. 51, no.12
pp. 4237-4246
[arXiv]
[doi]
[abstract]
Abstract:
We address the problem of bounding below the probability
of error under maximum likelihood decoding of a binary code with a
known distance distribution used on a binary symmetric channel. An
improved upper bound is given for the maximum attainable exponent of
this probability (the reliability function of the channel).
In particular, we prove that the ``random coding exponent'' is the true
value of the channel reliability for codes rate $R$ in some interval
immediately below the critical rate of the channel. An analogous result
is obtained for the Gaussian channel.
A. Barg and G. Zémor
(2005)
Concatenated codes: serial and parallel
IEEE Trans. Inf. Theory
vol. 51, no.12
pp. 4237-4246
A. Barg
(2004)
On the asymptotic accuracy of the union bound
Proc. 42nd Allerton Conference
[arXiv]
[abstract]
Abstract:
A new lower bound on the error probability of maximum likelihood decoding of a binary code on a binary symmetric channel was proved in Barg and McGregor (2004,
[arXiv]). It was observed in that paper that this bound leads to a new region of code rates in which the random coding exponent is asymptotically tight, giving a new region in which the reliability of the BSC is known exactly. The present paper explains the relation of these results to the union bound on the error probability.
A. Barg
(2004)
Improved bounds for the erasure/list scheme
IEEE Trans. Inf. Theory
vol. 50, no.10
pp. 2503-2514
A. Barg and G. Zémor
(2004)
Error exponents of expander codes under linear-time decoding
SIAM J. Discrete Math.
vol. 48, no. 6
pp. 426-445
[pdf]
[doi]
[abstract]
Abstract:
A class of codes is said to reach capacity $C$ of the binary symmetric channel if for any rate $R < C$ and any $\varepsilon > 0$ there is a sufficiently large $N$ such that codes of length $\ge N$ and rate R from this class provide error probability of decoding at most $\varepsilon$, under some decoding algorithm.
The study of the error probability of expander codes was initiated by Barg and Z{émor in 2002 [IEEE Trans. Inform. Theory, 48 (2002), pp. 1725--1729], where it was shown that they attain capacity of the binary symmetric channel under a linear-time iterative decoding with error probability falling exponentially with code length $N$. In this work we study variations on the expander code construction and focus on the most important region of code rates, close to the channel capacity. For this region we estimate the decrease rate (the error exponent) of the error probability of decoding for randomized ensembles of codes. The resulting estimate gives a substantial improvement of previous results for expander codes and some other explicit code families.
A. Barg and G. Kabatiansky
(2004)
A class of I.P.P. codes with efficient identification
Journal of Complexity
vol. 50, no.10
pp. 2503-2514
A. Barg, G. R. Blakley, and G. Kabatiansky
(2003)
Digital fingerprinting codes: Problem
statements, constructions, identification of traitors
IEEE Trans. Inf. Theory
vol. 49, no. 4
pp. 852-865
A. Ashikhmin and A. Barg
(2002)
Bounds on the covering radius of linear codes
Designs, Codes and Cryptography
vol. 27
pp. 261-269
A. Barg
(2002)
A low-rate bound on the reliability of a quantum discrete memoryless channel
IEEE Trans. Inf. Theory
vol. 48, no. 12
pp. 3096 - 3100
[arXiv]
[doi]
[abstract]
Abstract:
We extend a low-rate improvement of the random coding bound on the reliability of a classical discrete memoryless channel to its quantum counterpart. The key observation that we make is that the problem of bounding below the error exponent for a quantum channel relying on the class of stabilizer codes is equivalent to the problem of deriving error exponents for a certain symmetric classical channel.
A. Barg and D.Yu. Nogin
(2002)
Bounds on packings of spheres in the Grassmann manifolds
IEEE Trans. Inf. Theory
vol. 48, no. 9
pp. 2450–2454
[pdf]
[doi]
[abstract]
Abstract:
We derive the Gilbert-Varshamov and Hamming bounds for packings of spheres (codes) in the Grassmann manifolds over ${\mathbb R}$ and
$\mathbb C$. Asymptotic expressions are obtained for the geodesic metric and projection Frobenius (chordal) metric on the manifold.
[Erratum]
A. Barg and G. Zémor
(2002)
Error exponents of expander codes
IEEE Trans. Inf. Theory
vol. 48, no. 6
pp. 2450–2454
A. Barg and G.D. Forney
(2002)
Random codes: minimum distances and error exponents
IEEE Trans. Inf. Theory
vol. 48, no. 9
pp. 2568-2573
[pdf]
[doi]
[abstract]
Abstract:
Minimum distances, distance distributions, and error exponents on a
binary symmetric channel (BSC) are given for typical codes from Shannon's
random code ensemble and for typical codes from a random linear code
ensemble. A typical random code of length $N$ and rate $R$ is shown to
have minimum distance $N\delta_{\text{GV}}(2R)$, where $\delta_{\text{GV}}(R)$ is the Gilbert-Varshamov
relative distance at rate $R$, whereas a typical linear code has minimum distance $N\delta_{\text{GV}}(R)$.
Consequently, a typical linear code has a better error exponent on a BSC
at low rates, namely the expurgated error exponent.
A. Barg
(2002)
On some polynomials related to the weight enumerator of linear codes
SIAM J. Discrete Math.
vol. 15, no. 2
pp. 155-164
A. Barg
(2002)
Extremal problems of coding theory
in "Coding Theory and Cryptology", H. Niederreiter, Editor
World Scientific
pp. 1-48
A. Ashikhmin, A. Barg, and S. Litsyn
(2001)
Estimates of the distance distribution of codes and designs
vol. 47, no. 3
pp. 1050-1061
[pdf]
[doi]
[abstract]
Abstract:
We consider the problem of bounding the distance
distribution for unrestricted block codes with known distance
and/or dual distance. Applying the polynomial method, we provide
a general framework for previously known results. We derive
several upper and lower bounds both for finite length and for
sequences of codes of growing length. Asymptotic results in the
paper improve previously known estimates. In particular, we
prove the best known bounds on the binomiality range of the
distance spectrum of codes with a known dual distance.
A. Barg, G. Cohen, S. Encheva, G. Kabatiansky and G. Zémor
(2001)
A hypergraph approach to IPP codes: the case of multiple parents
SIAM J. Discrete Math.
vol. 14, no. 3
pp. 423-432
[pdf]
[doi]
[abstract]
Abstract:
Let $C$ be a code of length $n$ over an alphabet of $q$ letters. An $n$-word $y$ us called a descendant of a set of $t$ codewords $x^1,\dots, x^t$ if
$y_i\in\{x_i^1,\dots,x_i^t\}$ for all $i=1,\dots,n.$ A code is said to have the $t$-identifying parent property if for any $n$-word that is a descendant
of at most $t$ parents it is possible to identify at least one of them. We prove that for any $t\le q-1$ there exist sequences of such codes
with asymptotically nonvanishing rate.
A. Ashikhmin, A. Barg, and S. Vlăduţ
(2001)
Linear codes with exponentially many light vectors
Journal of Combinatorial Theory Series A
vol. 96, no. 2
pp. 396-399
[pdf]
[doi]
[abstract]
Abstract:
G. Kalai and N. Linial (1995, IEEE Trans. Inform. Theory, vol. 41, 1467–1472) put forward the following conjecture: Let $\{C_n\}$ be a sequence of binary linear codes of distance $d_n$ and let $A_{d_n}$ be the number of vectors of weight $d_n$ in $C_n$. Then $\log_2 A_{d_n}=o(n)$. We disprove this by constructing a family of linear codes from geometric Goppa codes in which the number of vectors of minimum weight grows exponentially with the length.
A. Barg, J. Justesen, and C. Thommesen
(2001)
Concatenated codes with fixed inner codes and random outer codes
IEEE Trans. Inf. Theory
vol. 47, no. 1
pp. 361-365
[pdf]
[doi]
[abstract]
Abstract:
We derive lower bounds on the distance and error exponent of the coding scheme described in the title. The bounds are compared to the parameters and error performance of a concatenated code family with varying inner codes of equal rates and a fixed minimum-distance separable (MDS) code as the outer code, letting the inner and outer code lengths approach infinity.
A. Ashikhmin, A. Barg, and S. Litsyn
(2000)
A new upper bound on codes decodable into size-2 lists
Numbers, Information and Complexity
Ingo Althoefer et al., Eds., Boston: Kluwer Publ.
pp. 239-244
A. Barg, S. Guritman, and J. Simonis
(2000)
Strengthening the Varshamov-Gilbert bound
Linear Alg. Appl.
vol. 307, no. 2
pp. 119-129
[pdf]
[doi]
[abstract]
Abstract:
G. Kalai and N. Linial (1995, IEEE Trans. Inform. Theory, vol. 41, 1467–1472) put forward the following conjecture: Let $\{C_n\}$ be a sequence of binary linear codes of distance $d_n$ and let $A_{d_n}$ be the number of vectors of weight $d_n$ in $C_n$. Then $\log_2 A_{d_n}=o(n)$. We disprove this by constructing a family of linear codes from geometric Goppa codes in which the number of vectors of minimum weight grows exponentially with the length.
A. Ashikhmin, A. Barg, E. Knill, and S. Litsyn
(2000)
Quantum error detection
Part I - Statement of the Problem IEEE Trans. Inf. Theory vol. 46, no. 5 pp. 778-788 Part II - Bounds IEEE Trans. Inf. Theory vol. 46, no. 5 pp. 789-800
[arXiv I]
[arXiv II]
[doi]
[abstract]
Abstract:
This paper is devoted to the problem of error detection with quantum codes. We show that it is possible to give a consistent definition of the undetected error event. To prove this, we examine possible problem settings for quantum error detection. Our goal is to derive a functional that describes the probability of undetected error under natural physical assumptions concerning transmission with error detection with quantum codes. We discuss possible transmission protocols with stabilizer and unrestricted quantum codes. The set of results proved in the paper shows that in all the cases considered the average probability of undetected error for a given code is essentially given by one and the same function of its weight enumerators. We examine polynomial invariants of quantum codes and show that coefficients of Rains's (T-IT, vol. 44, p.1388-1394, 1998) "unitary weight enumerators" are known for classical codes under the name of binomial moments of the distance distribution. As in the classical situation, these enumerators provide an alternative expression for the probability of undetected error.
A. Ashikhmin, A. Barg, and S. Litsyn
(1999)
A new upper bound on the reliability function of the Gaussian channel
IEEE Trans. Inf. Theory
vol. 45, no. 5
pp. 1945-1961
[pdf]
[doi]
[abstract]
Abstract:
We derive a new upper bound on the exponent of error probability of decoding for the best possible codes in the Gaussian channel. This bound is tighter than the known upper bounds (the sphere-packing and minimum-distance bounds proved in Shannon's classical 1959 paper and their low-rate improvement by Kabatiansky and Levenshtein (1978)). The proof is accomplished by studying asymptotic properties of codes on the sphere
$S^{n-1}({\mathbb R})$. First we prove a general lower bound on the distance distribution of codes of large size. To derive specific estimates of the distance distribution, we study the asymptotic behavior of Jacobi polynomials $P_k^{a_k,b_k}(t)$ as $k\to\infty.$
Since on the average there are many code vectors in the vicinity of the transmitted vector $x,$ one can show that the probability of confusing $x$ and one of these vectors cannot be too small. This proves a lower bound on the error probability of decoding and the upper bound announced in the title.
A. Barg and S. Zhou
(1999)
Linear-time binary codes correcting localized erasures
IEEE Trans. Inf. Theory
vol. 45, no. 7
pp. 2547-2552
A. Ashikhmin, A. Barg, and S. Litsyn
(1999)
New upper bounds on generalized weights
IEEE Trans. Inf. Theory
vol. 45, no. 4
pp. 2547-2552
A. Ashikhmin and A. Barg
(1999)
Binomial moments of the distance distribution: Bounds and applications
IEEE Trans. Inf. Theory
vol. 45, no. 4
pp.
A. Barg and A. Ashikhmin
(1999)
Binomial moments of the distance distribution and the
probability of undetected error
Designs, Codes and Cryptography
vol. 16
pp.
[doi]
[abstract]
Abstract:
In (T-IT vol. 43, no. 5, 1997) K. A. S. Abdel-Ghaffar derives a lower bound on the probability of undetected error for unrestricted codes. The proof relies implicitly on the binomial moments of the distance distribution of the code. We use the fact that these moments count the size of subcodes of the code to give a very simple proof of the bound of Abdel-Ghaffar by showing that it is essentially equivalent to the Singleton bound. This proof reveals connections of the probability of undetected error to the rank generating function of the code and to related polynomials (Whitney function, Tutte polynomial, and higher weight enumerators). We also discuss some improvements of this bound.
A. Ashikhmin and A. Barg
(1998)
Minimal vectors in linear codes
IEEE Trans. Inf. Theory
vol. 44, no. 5
pp. 2010 - 2017
[pdf]
[doi]
[abstract]
Abstract:
Minimal vectors in linear codes arise in numerous applications, particularly, in constructing decoding algorithms and studying linear secret sharing schemes. However, properties and structure of minimal vectors have been largely unknown. We prove basic properties of minimal vectors in general linear codes. Then we characterize minimal vectors of a given weight and compute their number in several classes of codes, including the Hamming codes and second-order Reed-Muller codes. Further, we extend the concept of minimal vectors to codes over rings and compute them for several examples. Turning to applications, we introduce a general gradient-like decoding algorithm of which minimal-vectors decoding is an example. The complexity of minimal-vectors decoding for long codes is determined by the size of the set of minimal vectors. Therefore, we compute this size for long randomly chosen codes.
(in late 2010s there has been renewed interest in this work; there is now a multitude of papers on minimal codes).
A. Barg and S. Zhou
(1998)
A quantum decoding algorithm of the simplex code
Allerton Conference
A. Barg
(1997)
The matroid of supports of a linear code
Applied Alg. in Commun. Comput.
vol. 8
pp. 165-172
[pdf]
[doi]
[abstract]
Abstract:
A relation between the Hamming weight enumerator of a linear code and the Tutte polynomial of the corresponding matroid has been known since long ago. It provides a simple proof of the MacWilliams equation (see D. Welsh, Matroid Theory (1976)). In this paper we prove analogous results for the support weight distributions of a code.
A. Barg, G. Katsman, and M. Tsfasman
(1987)
Algebrogeometric codes from curves of small genus
Probl. Inform. Trans.
vol. 23, no. 1
pp. 34-38
[pdf]
[abstract]
Abstract:
We construct $q$-ary codes obtained from curves of genus 1,2, and 3. These codes are used to construct binary codes with parameters better than the known codes.
Some talks and tutorialsWhat can and what cannot be done with LP and SDP, Simons Inst., UC Berkeley, 2024 [video] Stolarsky's invariance principle in finite metric spaces, 2020 [slides] [video] Erasure codes for distributed storage and related problems 2019 IEEE North Americal School on Information Theory (slides and video at NASIT'19) Estimation of discrete distributions under local differential privacy [slides] Codes, metrics, and applications, Plenary at ISIT 2016 slides, video Tutorial on codes with locality constraints, ISIT 2016, Barcelona (joint with Itzhak Tamo) Infinite association schemes: New applications of harmonic analysis in combinatorics, UMD Norbert Wiener Center (2015). YouTube Books edited |
Alexander Barg
Home
Research
Publications
Students
Teaching
Editorial Boards
Seminar
Contact
Office: AVW 2361
Phone: +1 301 405 7135
[abarg@umd.edu]
Postal address:
Department of ECE
University of Maryland
8223 Paint Branch Dr.
College Park, MD 20742, USA
Phone: +1 301 405 7135
[abarg@umd.edu]
Postal address:
Department of ECE
University of Maryland
8223 Paint Branch Dr.
College Park, MD 20742, USA