Publications (95)
Explicit constructions of MSR codes for clustered distributed storage: The rack-aware storage model
Zitan Chen, Alexander Barg
The paper is devoted to the problem of erasure coding in distributed storage. We consider a model of storage that assumes that nodes are organized into equally sized groups, called…
Asymptotically good bosonic Fock state codes
Dor Elimelech, Arda Aydin, Alexander Barg
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 c…
Linear codes on posets with extension property
Alexander Barg, Luciano V. Felix, Marcelo Firer +1
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…
Smoothing of binary codes, uniform distributions, and applications
Madhura Pathegama, Alexander Barg
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…
The repair problem for Reed-Solomon codes: Optimal repair of single and multiple erasures, asymptotically optimal node size
Itzhak Tamo, Min Ye, Alexander Barg
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…
New bounds for spherical two-distance sets
Alexander Barg, Wei-Hsuan Yu
A spherical two-distance set is a finite collection of unit vectors in such that the set of distances between any two distinct vectors has cardinality two. We use the se…
Codes in spherical caps
Alexander Barg, Oleg R. Musin
We consider bounds on codes in spherical caps and related problems in geometry and coding theory. An extension of the Delsarte method is presented that relates upper bounds on the…
On the asymptotic accuracy of the union bound
Alexander Barg
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, cs.IT/0407011). It w…
Storage codes on coset graphs with asymptotically unit rate
Alexander Barg, Moshe Schwartz, Lev Yohananov
A storage code on a graph 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…
Near MDS poset codes and distributions
Alexander Barg, Punarbasu Purkayastha
We study -ary codes with distance defined by a partial order of the coordinates of the codewords. Maximum Distance Separable (MDS) codes in the poset metric have been studied in…
Bounds for the sum of distances of spherical sets of small size
Alexander Barg, Peter Boyvalenkov, Maya Stoyanova
We derive upper and lower bounds on the sum of distances of a spherical code of size in dimensions when The bounds are derived by specializing rece…
Bounds on the Parameters of Locally Recoverable Codes
Itzhak Tamo, Alexander Barg, Alexey Frolov
A locally recoverable code (LRC code) is a code over a finite alphabet such that every symbol in the encoding is a function of a small number of other symbols that form a recoverin…
Polar Codes for Distributed Hierarchical Source Coding
Min Ye, Alexander Barg
We show that polar codes can be used to achieve the rate-distortion functions in the problem of hierarchical source coding also known as the successive refinement problem. We also…
Regular LDPC codes on BMS wiretap channels: Security bounds
Madhura Pathegama, Alexander Barg
We improve the secrecy guarantees for transmission over general binary memoryless symmetric wiretap channels that relies on regular LDPC codes. Previous works showed that LDPC code…
A functional view of upper bounds on codes
Alexander Barg, Dmitry Nogin
Functional and linear-algebraic approaches to the Delsarte problem of upper bounds on codes are discussed. We show that Christoffel-Darboux kernels and Levenshtein polynomials rela…
Minimum distance and decoding of Coxeter codes
Alexander Barg, Qëndrim R. Gashi, Tianyuan Xu
A binary Coxeter code associated with a finite Coxeter system is an -linear span of indicators of standard cosets of a fixed rank. Coxeter codes, introduced…
Storage codes and recoverable systems on lines and grids
Alexander Barg, Ohad Elishco, Ryan Gabrys +2
A storage code is an assignment of symbols to the vertices of a connected graph with the property that the value of each vertex is a function of the values of its neighbor…
New bounds for equiangular lines
Alexander Barg, Wei-Hsuan Yu
A set of lines in is called equiangular if the angle between each pair of lines is the same. We address the question of determining the maximum size of equiangular l…
Error correction based on partial information
Itzhak Tamo, Min Ye, Alexander Barg
We consider the decoding of linear and array codes from errors when we are only allowed to download a part of the codeword. More specifically, suppose that we have encoded data…
Interactive Function Computation via Polar Coding
Talha Cihad Gulcu, Alexander Barg
In a series of papers N. Ma and P. Ishwar (2011-13) considered a range of distributed source coding problems that arise in the context of iterative computation of functions, charac…
Recoverable Systems
Ohad Elishco, Alexander Barg
Motivated by the established notion of storage codes, we consider sets of infinite sequences over a finite alphabet such that every -tuple of consecutive entries is uniquely rec…
A bound on Grassmannian codes
Alexander Barg, Dmitry Nogin
We give a new asymptotic upper bound on the size of a code in the Grassmannian space. The bound is better than the upper bounds known previously in the entire range of distances ex…
Cyclic and convolutional codes with locality
Zitan Chen, Alexander Barg
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…
Distance distribution of binary codes and the error probability of decoding
Alexander Barg, Andrew McGregor
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 c…
Improved error bounds for the erasure/list scheme: the binary and spherical cases
Alexander Barg
We derive improved bounds on the error and erasure rate for spherical codes and for binary linear codes under Forney's erasure/list decoding scheme and prove some related results.
Generalized regenerating codes and node repair on graphs
Adway Patra, Alexander Barg
We consider regenerating codes in distributed storage systems where connections between the nodes are constrained by a graph. In this problem, the failed node downloads the informa…
Node repair on connected graphs
Adway Patra, Alexander Barg
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…
Bounds on Locally Recoverable Codes with Multiple Recovering Sets
Itzhak Tamo, Alexander Barg
A locally recoverable code (LRC code) is a code over a finite alphabet such that every symbol in the encoding is a function of a small number of other symbols that form a recoverin…
Locally recoverable codes from algebraic curves and surfaces
Alexander Barg, Kathryn Haymaker, Everett W. Howe +2
A locally recoverable code is a code over a finite alphabet such that the value of any single coordinate of a codeword can be recovered from the values of a small subset of other c…
A family of optimal locally recoverable codes
Itzhak Tamo, Alexander Barg
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 ) other symbols. We present a family o…
Bounds on ordered codes and orthogonal arrays
Alexander Barg, Punarbasu Purkayastha
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 t…
Enabling optimal access and error correction for the repair of Reed-Solomon codes
Zitan Chen, Min Ye, Alexander Barg
Recently Reed-Solomon (RS) codes were shown to possess a repair scheme that supports repair of failed nodes with optimal repair bandwidth. In this paper, we extend this result in t…
A construction of maximally recoverable codes
Alexander Barg, Zitan Chen, Itzhak Tamo
We construct a family of linear maximally recoverable codes with locality and dimension For codes of length with the code alphabet is of…
Breaking the bicycle frame: Coset-based quantum LDPC codes
Arda Aydin, Itzhak Tamo, Alexander Barg
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 o…
Finite two-distance tight frames
Alexander Barg, Alexei Glazyrin, Kasso Okoudjou +1
A finite collection of unit vectors is called a spherical two-distance set if there are two numbers and such that the inner products of distinct ve…
Coxeter codes: Extending the Reed-Muller family
Nolan J. Coble, Alexander Barg
Binary Reed-Muller (RM) codes are defined via evaluations of Boolean-valued functions on . We introduce a class of binary linear codes that generalizes the RM famil…
Cyclic LRC Codes and their Subfield Subcodes
Itzhak Tamo, Alexander Barg, Sreechakra Goparaju +1
We consider linear cyclic codes with the locality property, or locally recoverable codes (LRC codes). A family of LRC codes that generalizes the classical construction of Reed-Solo…
Targeted Clifford logical gates for hypergraph product codes
Adway Patra, Alexander Barg
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 matri…
Optimal LRC codes for all lenghts n <= q
Oleg Kolosov, Alexander Barg, Itzhak Tamo +1
A family of distance-optimal LRC codes from certain subcodes of -ary Reed-Solomon codes, proposed by I.~Tamo and A.~Barg in 2014, assumes that the code length is a multiple…
Stolarsky's invariance principle for finite metric spaces
Alexander Barg
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…
Codes with hierarchical locality from covering maps of curves
Sean Ballentine, Alexander Barg, Serge Vladuts
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 w…
A family of permutationally invariant quantum codes
Arda Aydin, Max A. Alekseyev, Alexander Barg
We construct a new family of permutationally invariant codes that correct Pauli errors for any . We also show that codes in the new family correct quantum deletion erro…
On the Fingerprinting Capacity Under the Marking Assumption
N. Prasanth Anthapadmanabhan, Alexander Barg, Ilya Dumer
We address the maximum attainable rate of fingerprinting codes under the marking assumption, studying lower and upper bounds on the value of the rate for various sizes of the attac…
Bounds on sets with few distances
Alexander Barg, Oleg R. Musin
We derive a new estimate of the size of finite sets of points in metric spaces with few distances. The following applications are considered: (1) we improve the Ray-Chaudhuri--Wils…
Universal Source Polarization and an Application to a Multi-User Problem
Min Ye, Alexander Barg
We propose a scheme that universally achieves the smallest possible compression rate for a class of sources with side information, and develop an application of this result for a j…
Geometric structure and transversal logic of quantum Reed-Muller codes
Alexander Barg, Nolan J. Coble, Dominik Hangleiter +1
Designing efficient and noise-tolerant quantum computation protocols generally begins with an understanding of quantum error-correcting codes and their native logical operations. T…
Codes on hypergraphs
Alexander Barg, Arya Mazumdar, Gilles Zémor
Codes on hypergraphs are an extension of the well-studied family of codes on bipartite graphs. Bilu and Hoory (2004) constructed an explicit family of codes on regular t-partite hy…
Construction of polar codes for arbitrary discrete memoryless channels
Talha Cihad Gulcu, Min Ye, Alexander Barg
It is known that polar codes can be efficiently constructed for binary-input channels. At the same time, existing algorithms for general input alphabets are less practical because…
Polar codes for q-ary channels, q=2^r
Woomyoung Park, Alexander Barg
We study polarization for nonbinary channels with input alphabet of size q=2^r,r=2,3,... Using Arikan's polarizing kernel H_2, we prove that the virtual channels that arise in the…
Multilevel expander codes
Alexander Barg, Gilles Zemor
We define multilevel codes on bipartite graphs that have properties analogous to multilevel serial concatenations. A decoding algorithm is described that corrects a proportion of e…
Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization
Min Ye, Alexander Barg
An MDS array code of length dimension and sub-packetization is formed of matrices over a finite field with every column of the matrix st…
Explicit constructions of high-rate MDS array codes with optimal repair bandwidth
Min Ye, Alexander Barg
Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure-tolerance for a given number of parity nodes. Suppose t…
Recoverable systems and the maximal hard-core model on the triangular lattice
Geyang Wang, Alexander Barg, Navin Kashyap
In a previous paper (arXiv:2510.19746), we have studied the maximal hard-code model on the square lattice from the perspective of recoverable systems. Here we exten…
Distance properties of expander codes
Alexander Barg, Gilles Zemor
We study the minimum distance of codes defined on bipartite graphs. Weight spectrum and the minimum distance of a random ensemble of such codes are computed. It is shown that if th…
On the size of maximal binary codes with 2, 3, and 4 distances
Alexander Barg, Alexey Glazyrin, Wei-Jiun Kao +3
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 e…
Bounds for discrepancies in the Hamming space
Alexander Barg, Maxim Skriganov
We derive bounds for the ball -discrepancies in the Hamming space for and . Sharp estimates of discrepancies have been obtained for many spaces such as…
High-rate storage codes on triangle-free graphs
Alexander Barg, Gilles Zémor
Consider an assignment of bits to the vertices of a connected graph with the property that the value of each vertex is a function of the values of its neighbors. A collect…
Randomized Frameproof Codes: Fingerprinting Plus Validation Minus Tracing
N. Prasanth Anthapadmanabhan, Alexander Barg
We propose randomized frameproof codes for content protection, which arise by studying a variation of the Boneh-Shaw fingerprinting problem. In the modified system, whenever a user…
Cyclic LRC Codes, binary LRC codes, and upper bounds on the distance of cyclic codes
Itzhak Tamo, Alexander Barg, Sreechakra Goparaju +1
We consider linear cyclic codes with the locality property, or locally recoverable codes (LRC codes). A family of LRC codes that generalize the classical construction of Reed-Solom…
Theory of approximate quantum error correction and the error-set model
Dor Elimelech, Victor V. Albert, Alexander Barg
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 erro…
Association schemes on general measure spaces and zero-dimensional Abelian groups
Alexander Barg, Maxim Skriganov
Association schemes form one of the main objects of algebraic combinatorics, classically defined on finite sets. In this paper we define association schemes on arbitrary, possibly…
On the Number of Errors Correctable with Codes on Graphs
Alexander Barg, Arya Mazumdar
We study ensembles of codes on graphs (generalized low-density parity-check, or LDPC codes) constructed from random graphs and fixed local constrained codes, and their extension to…
Quantum error correction beyond : spin, bosonic, and permutation-invariant codes from convex geometry
Arda Aydin, Victor V. Albert, Alexander Barg
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 qudit…
Two-Level Fingerprinting Codes
N. Prasanth Anthapadmanabhan, Alexander Barg
We introduce the notion of two-level fingerprinting and traceability codes. In this setting, the users are organized in a hierarchical manner by classifying them into various group…
Constructions of Rank Modulation Codes
Arya Mazumdar, Alexander Barg, Gilles Zémor
Rank modulation is a way of encoding information to correct errors in flash memory devices as well as impulse noise in transmission lines. Modeling rank modulation involves constru…
Rényi divergence-based uniformity guarantees for -universal hash functions
Madhura Pathegama, Alexander Barg
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…
Optimal repair of Reed-Solomon codes: Achieving the cut-set bound
Itzhak Tamo, Min Ye, Alexander Barg
Coding for distributed storage gives rise to a new set of problems in coding theory related to the need of reducing inter-node communication in the system. A large number of recent…
Performance Analysis of Algebraic Soft-Decision Decoding of Reed-Solomon Codes
Andrew Duggan, Alexander Barg
We investigate the decoding region for Algebraic Soft-Decision Decoding (ASD) of Reed-Solomon codes in a discrete, memoryless, additive-noise channel. An expression is derived for…
Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes
Abhishek Agarwal, Alexander Barg, Sihuang Hu +2
Locally recoverable (LRC) codes have recently been a focus point of research in coding theory due to their theoretical appeal and applications in distributed storage systems. In an…
Limitations of the decoding-to-LPN reduction via code smoothing
Madhura Pathegama, Alexander Barg
The Learning Parity with Noise (LPN) problem underlines several classic cryptographic primitives. Researchers have attempted to demonstrate the algorithmic hardness of this problem…
Semidefinite programming bounds for few-distance sets in the Hamming and Johnson spaces
Alexander Barg, Ching-Yi Lai, Pin-Chieh Tseng +1
We study the maximum cardinality problem of a set of few distances in the Hamming and Johnson spaces. We formulate semidefinite programs for this problem and extend the 2011 works…
Repairing Reed-Solomon codes: Universally achieving the cut-set bound for any number of erasures
Min Ye, Alexander Barg
The repair bandwidth of a code is the minimum amount of data required to repair one or several failed nodes (erasures). For MDS codes, the repair bandwidth is bounded below by the…
Locally recoverable codes on algebraic curves
Alexander Barg, Itzhak Tamo, Serge Vladut
A code over a finite alphabet is called locally recoverable (LRC code) if every symbol in the encoding is a function of a small number (at most r) other symbols. A family of linear…
Asymptotically optimal private estimation under mean square loss
Min Ye, Alexander Barg
We consider the minimax estimation problem of a discrete distribution with support size under locally differential privacy constraints. A privatization scheme is applied to eac…
Optimal locally private estimation under loss for
Min Ye, Alexander Barg
We consider the minimax estimation problem of a discrete distribution with support size under locally differential privacy constraints. A privatization scheme is applied to eac…
Group testing schemes from codes and designs
Alexander Barg, Arya Mazumdar
In group testing, simple binary-output tests are designed to identify a small number of defective items that are present in a large population of items. Each test takes as…
Coding for High-Density Recording on a 1-D Granular Magnetic Medium
Arya Mazumdar, Alexander Barg, Navin Kashyap
In terabit-density magnetic recording, several bits of data can be replaced by the values of their neighbors in the storage medium. As a result, errors in the medium are dependent…
Node repair on connected graphs, Part II
Adway Patra, Alexander Barg
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 download…
Codes in Permutations and Error Correction for Rank Modulation
Alexander Barg, Arya Mazumdar
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, representi…
Restricted isometry property of random subdictionaries
Alexander Barg, Arya Mazumdar, Rongrong Wang
We study statistical restricted isometry, a property closely related to sparse signal recovery, of deterministic sensing matrices of size . A matrix is said to have a s…
Cooperative repair: Constructions of optimal MDS codes for all admissible parameters
Min Ye, Alexander Barg
Two widely studied models of multiple-node repair in distributed storage systems are centralized repair and cooperative repair. The centralized model assumes that all the failed no…
A Study on the Impact of Locality in the Decoding of Binary Cyclic Codes
M. Nikhil Krishnan, Bhagyashree Puranik, P. Vijay Kumar +2
In this paper, we study the impact of locality on the decoding of binary cyclic codes under two approaches, namely ordered statistics decoding (OSD) and trellis decoding. Given a b…
Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy
Min Ye, Alexander Barg
We consider the minimax estimation problem of a discrete distribution with support size under privacy constraints. A privatization scheme is applied to each raw sample independ…
Quantum spherical codes
Shubham P. Jain, Joseph T. Iosue, Alexander Barg +1
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…
Quantum Error Detection I: Statement of the Problem
Alexei Ashikhmin, Alexander Barg, Emanuel Knill +1
I. This paper is devoted to the problem of error detection with quantum codes. In the first part we examine possible problem settings for quantum error detection. Our goal is to de…
A low-rate bound on the reliability of a quantum discrete memoryless channel
Alexander Barg
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 ma…
Spectral approach to linear programming bounds on codes
Alexander Barg, Dmitry Nogin
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…
Secret Key Generation for a Pairwise Independent Network Model
Sirin Nitinawarat, Chunxuan Ye, Alexander Barg +2
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 b…
The maximal hard-core model as a recoverable system: Gibbs measures and phase coexistence
Geyang Wang, Alexander Barg, Navin Kashyap
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 specif…
Class of codes correcting absorptions and emissions
Arda Aydin, Alexander Barg
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…
Rényi divergence guarantees for hashing with linear codes
Madhura Pathegama, Alexander Barg
We consider the problem of distilling uniform random bits from an unknown source with a given -entropy using linear hashing. As our main result, we estimate the expected -div…
Capacity of dynamical storage systems
Ohad Elishco, Alexander Barg
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 mai…
Locally recoverable codes on algebraic curves
Alexander Barg, Itzhak Tamo, Serge Vladuts
A code over a finite alphabet is called locally recoverable (LRC code) if every symbol in the encoding is a function of a small number (at most ) other symbols of the codeword.…
Random Subdictionaries and Coherence Conditions for Sparse Signal Recovery
Alexander Barg, Arya Mazumdar, Rongrong Wang
The most frequently used condition for sampling matrices employed in compressive sampling is the restricted isometry (RIP) property of the matrix when restricted to sparse signals.…
Achieving Secrecy Capacity of the Wiretap Channel and Broadcast Channel with a Confidential Component
Talha Cihad Gulcu, Alexander Barg
The wiretap channel model of Wyner is one of the first communication models with both reliability and security constraints. Capacity-achieving schemes for various models of the wir…