## Preprints
A. Patra and A. Barg
(2022)
Interior-point regenerating codes on graphs
submitted for publication
[abstract]
Abstract:
We consider the use of regenerating codes in distributed storage systems where connections between the nodes are constrained by
a graph. In this setting the cost of node repair is determined by the graphical distance from the helper nodes to the failed node.
In our recent work (arXiv:2108:00939) we considered the MSR case, showing that linear MSR codes are amenable to intermediate processing
of the information, resulting in reduced repair bandwidth which also meets the lower bound on the minimum repair cost.
Here we extend this study to the non-MSR case. 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 intermediate processing for the problem of partial node repair.
A. Barg, O. Elishco, R. Gabrys, and E. Yaakobi
(2022)
Recoverable systems on lines and grids
submitted for publication
[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$.
Under the name of recoverable systems, a class of storage codes on ${\mathbb Z}$ was recently studied
relying on methods from constrained systems and ergodic theory. In this work, we address the question of
the maximum capacity of recoverable systems on ${\mathbb Z}$ and ${\mathbb Z}^2$ from a combinatorial perspective. We establish a closed form formula 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 and G. Zémor
(2021)
High-rate storage codes on triangle-free graphs
submitted for publication
[arXiv]
[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.
A. Barg, P. Boyvalenkov, and M. Stoyanova
(2021)
Bounds for the sum of distances of spherical sets of small size
submitted for publication
[arXiv]
[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.
## Published/accepted
A. Patra and A. Barg
(2022)
Node repair on connected graphs
IEEE Transactions on Information Theory
[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.
O Elishco, A. Barg
(2022)
Recoverable systems
IEEE Transactions on Information Theory
[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. Barg, Z. Chen, and I. Tamo
(2022)
A construction of maximally recoverable codes
Designs, Codes and Cryptography
[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
(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. click to see more/fewer items]
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.
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.
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 tutorialsStolarsky'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 |