Codes with locality without any global paritycheck constraints apart from those generated by local codes' constraints have recently found a unique application in decentralized systems. In response to this, we proposed in previous work, a new class of block circulant (BC) codes possessing certain structure in the arrangement of parity-check constraints referred to as a block circulant topology. The BC topology$T_{[\mu, \lambda, \omega]}(\rho)$and$\mathbf{B C}$codes$C_{\mathbf{B C}}[\mu, \lambda, \omega, \rho]$are parameterized by integers$\lambda \geq 2, \omega \geq 2, \rho \geq 2$and$\mu$a multiple of$\lambda$. In this work, we show that the rate and the minimum distance of the BC code scale with corresponding metrics of its local codes in a manner that can not be realized by well-known linear array and product topologies, thus widening the possible regime of operation. We also provide an efficient erasure-correcting decoder for$C_{\mathbf{B C}}[\mu, \lambda=3, \omega, \rho]$, while such a decoder was earlier known only for$\lambda=2$. The decoding algorithm uses a novel mechanism that iteratively corrects erasures from either a single or a triplet of local codes. We show that the minimum distance of$C_{\mathbf{B C}}[\mu, \lambda=3, \omega, \rho]$is$3 \rho+1$, whereas the same result was earlier available under a constraint that$\mu=2^{a} \cdot 3$for some integer$a$.

A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch - Pirare based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that zero storage overhead is achievable for tree-shaped databases. In particular, we develop TreePIR, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no storage redundancy. This type of tree has been widely implemented in many real-world systems such as Amazon DynamoDB, Google's Certificate Transparency, and blockchains. Tree nodes along a root-to-leaf path forms the well-known Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel et al. S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving 3 ×lower total storage and 1.5-3 ×lower computation and communication costs. Most notably, TreePIR has 8-160× lower setup time and its polylog-complexity indexing algorithm is 19–160 ×faster than PBC for trees of 210_224leaves.

We explored the ubiquitous phenomenon of serial scammers, each of whom deployed dozens to thousands of addresses to conduct a series of similar Rug Pulls on popular decentralized exchanges.We first constructed two datasets of around 384,000 scammer addresses behind all one-day Simple Rug Pulls on Uniswap (Ethereum) and Pancakeswap (BSC), and identified distinctive scam patterns including star, chain, and major (scam-funding) flow.These patterns, which collectively cover about 40% of all scammer addresses in our datasets, reveal typical ways scammers run multiple Rug Pulls and organize the money flow among different addresses.We then studied the more general concept of scam cluster, which comprises scammer addresses linked together via direct ETH/BNB transfers or behind the same scam pools.We found that scam token contracts are highly similar within each cluster (average similarities > 70%) and dissimilar across different clusters (average similarities < 30%), corroborating our view that each cluster belongs to the same scammer/scam organization.Lastly, we analyze the scam profit of individual scam pools and clusters, employing a novel cluster-aware profit formula that takes into account the important role of wash traders.The analysis shows that the existing formula inflates the profit by at least 32% on Uniswap and 24% on Pancakeswap.

Satellite communication (SatCom) systems play a vital role in providing global connectivity and enable a wide range of applications, including Internet of Things (IoT) connectivity for remote areas, such as forests and oceans. Two crucial resource allocation challenges in SatCom are beam placement (BP) and frequency assignment (FA) problems, which involve the clique covering (CC) and graph coloring (GC) problems, respectively. Conventional solutions for these problems incur excessive computational cost, which is intractable for classical computers. A promising approach is to formulate these problems using the Ising model, construct their Hamiltonians, and then solve them efficiently by a quantum computer. However, the current quantum computers have very limited hardware and can only handle rather small inputs. To overcome this limitation, we propose a hybrid-quantum-classical-computational pipeline where an efficient hamiltonian reduction method is the key for solving large CC/GC instances. Through experiments on real quantum computers, our reduction method outperforms commercial solutions, allowing quantum annealers to handle significantly larger BP/FA instances while maintaining high probability to achieve feasible solutions and near-optimal performance. Although the inherent hardness of the CC/GC problems cannot be overcome by quantum computing, our research contributes to the early exploration of quantum computing in the context of the complex optimization problems in SatCom systems, particularly in the realm of IoT connectivity for remote areas.

In this paper, we design a family of [n, k, d] block circulant codes that consist of many [n0≪n, k0≪k, d0d] local codes and that satisfy two properties: (1) the code supports distributed decoding of up to (d− 1) erasures relying only on local codes without a central coordinator, and (2) it is amenable to low complexity verification of code symbols using a cryptographic commitment scheme. These properties make the code ideal for use in protocols that address the data availability problem in blockchain networks. Moreover, the code outperforms the currently used 2D Reed-Solomon (RS) code with a larger relative minimum distance (d/n), as desired in the protocol, for a given rate (k/n) in the high-rate regime. The code is designed in two steps. First, we develop the topology, i.e., the structure of linear dependence relations among code symbols, and define it as the block circulant topologyT[μ,λ,ω](ρ). In this topology, there are μ local codes, each constrained by ρ parity checks. The set of symbols of a local code intersects with another in a uniform pattern, determined by two parameters, namely theoverlap factorλ and theoverlap widthω. Next, we instantiate the topology, i.e., specify the coefficients of the linear dependence relations, to construct the block circulant codesCBC[μ, λ, ω, ρ]. Every local code is a [λω+ρ, λω, ρ+1] generalized RS code. The block circulant code hasn= μ(ρ + ω), k = μω and we show that, under certain conditions,d= λρ + 1. For λ = 2, we prove that d = 2ρ+1 always, and provide an efficient, parallelizable erasure-correcting decoder that fully recovers the codeword when there are ≤ 2ρ erasures. The decoder uses a novel decoding mechanism that iteratively recovers erasures from either local codes or pairs of them.

We investigate the problems of privately repairing erasures and evaluating their linear combinations for Reed-Solomon codes with low communication bandwidths. We propose two approaches: one based on hiding subspaces used to form parity-check equations, and another based on multiplying parity-check equations with random polynomials. We also derive a lower bound on the repair bandwidth for the single erasure case under reasonable assumptions about the schemes being used and demonstrate the optimality of the proposed schemes for codes of specific lengths.

To measure repair latency at helper nodes, we introduce a new metric called skip cost that quantifies the number of contiguous sections accessed on a disk. We provide explicit constructions of zigzag codes and fractional repetition codes that incur zero skip cost.

We investigate the problem of privately recovering a single erasure for Reed-Solomon codes with low communication bandwidths. For an$[n,k]_{\mathbb{F}_{q^{\ell}}}$code with$n-k\geq q^{m}+t-1$, we construct a repair scheme that allows a client to recover an arbitrary codeword symbol without leaking its index to any set of$t$colluding helper nodes at a repair bandwidth of$(n-1)(\ell-m)$sub-symbols in$\mathbb{F}_{q}$. When$t=1$, this reduces to the bandwidth of existing repair schemes based on subspace polynomials. We prove the optimality of the proposed scheme when$n=q^{\ell}$under a reasonable assumption about the schemes being used. Our private repair scheme can also be transformed into a private retrieval scheme for data encoded by Reed-Solomon codes.

A family of$(n=2^{\ell}.M=2^{k_{\ell}}\ . \ d=2)$, binary constant-weight codes for any positive integer$\ell > 3, k_{\ell}= \displaystyle \frac{\ell(\ell+1)}{9}-1$was recently proposed in literature [1]. As infor-mation is encoded in the gaps (cyclically counted) between successive 1 's, we refer to these codes as cyclic-gap constant weight codes denoted by$C_{G}[\ell$. These codes admit very low-complexity algorithms for mapping and demapping between message and codeword vectors, fully eliminating the need for costly computations of binomial coefficients. In this paper, we study maximum-likelihood (ML) decoding of these codes under additive white Gaussian noise channels. Since the minimum distance of the code$d=2$, hard-decision decoders can not correct errors. Motivated by the error-correcting capability of soft-decision Wagner-rule decoder for single-parity-check codes, we derive an ML decoder for$C_{G}[\ell$. We also derive a low-complexity approximation of the ML decoder with a time-complexity of$O(n\log n^{\backslash },$. The algorithm is based on a novel technique of traversal through the Hasse diagram of a partially ordered set of all ℓ-subsets of$\{1, 2, \ldots, n\}$in a breadth-first manner. Our approach is applicable to decoding of any binary constant-weight code and therefore is of general interest. We simulate the performance of the low-complexity decoder for the$(8, 32, 2)$code$C_{G}$[3] and show that it performs almost similar to ML when a parameter$\lambda_{\mathrm{m}\mathrm{m}}$(that determines how far to traverse in the Hasse diagram) is taken to be 3. We also show by simulation that it performs better than a comparable$[8, 5, 2]$linear code under ML decoding.

We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set$S$of linearly independent combinations of the sub-symbols of the lost symbol. When$S=\varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When$S$is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on$\vert S\vert$and not the content of$S$and construct a lower bound on the repair bandwidth of a linear repair scheme with side information$S$We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes.

Abstract In this paper, we focus on the design of binary constant weight codes that admit low-complexity encoding and decoding algorithms, and that have size $$M=2^k$$ M = 2 k so that codewords can conveniently be labeled with binary vectors of length k. For every integer $$\ell \ge 3$$ ℓ ≥ 3 , we construct a $$(n=2^\ell , M=2^{k_{\ell }}, d=2)$$ ( n = 2 ℓ , M = 2 k ℓ , d = 2 ) constant weight code $${{{\mathcal {C}}}}[\ell ]$$ C [ ℓ ] of weight $$\ell $$ ℓ by encoding information in the gaps between successive 1’s of a vector, and call them as cyclic-gap constant weight codes. The code is associated with a finite integer sequence of length $$\ell $$ ℓ satisfying a constraint defined as anchor-decodability that is pivotal to ensure low complexity for encoding and decoding. The time complexity of the encoding algorithm is linear in the input size k, and that of the decoding algorithm is poly-logarithmic in the input size n, discounting the linear time spent on parsing the input. Both the algorithms do not require expensive computation of binomial coefficients, unlike the case in many existing schemes. Among codes generated by all anchor-decodable sequences, we show that $${{{\mathcal {C}}}}[\ell ]$$ C [ ℓ ] has the maximum size with $$k_{\ell } \ge \ell ^2-\ell \log _2\ell + \log _2\ell - 0.279\ell - 0.721$$ k ℓ ≥ ℓ 2 - ℓ log 2 ℓ + log 2 ℓ - 0.279 ℓ - 0.721 . As k is upper bounded by $$\ell ^2-\ell \log _2\ell +O(\ell )$$ ℓ 2 - ℓ log 2 ℓ + O ( ℓ ) information-theoretically, the code $${{{\mathcal {C}}}}[\ell ]$$ C [ ℓ ] is optimal in its size with respect to two higher order terms of $$\ell $$ ℓ . In particular, $$k_\ell $$ k ℓ meets the upper bound for $$\ell =3$$ ℓ = 3 and one-bit away for $$\ell =4$$ ℓ = 4 . On the other hand, we show that $${{{\mathcal {C}}}}[\ell ]$$ C [ ℓ ] is not unique in attaining $$k_{\ell }$$ k ℓ by constructing an alternate code $$\mathcal{{\hat{C}}}[\ell ]$$

Private Information Retrieval (PIR) protocols allow a client to retrieve any file of interest while keeping the files identity hidden from the database servers. While many existing PIR protocols assume servers to be honest but curious, we investigate the scenario of dishonest servers that provide incorrect answers to mislead clients into obtaining wrong results. We propose a unified framework for polynomial PIR protocols encompassing various existing protocols that optimize the download rate or total communication cost. We introduce a way to transform a polynomial PIR to a verifiable one without increasing the number of involved servers by doubling the queries. The security guarantees can be information-theoretic or computational, and the verification keys can be public or private. Moreover, in one of our protocols, the ratio between the additional download overhead associated with verification and the normal download cost approaches zero as the file size goes to infinity.

Beam Placement (BP) is a well-known problem in Low-Earth Orbit (LEO) satellite communication (SatCom) systems, which can be modelled as an NP-hard clique cover problem. Recently, quantum computing has emerged as a novel technology which revolutionizes how to solve challenging optimization problems by formulating Quadratic Unconstrained Binary Optimization (QUBO), then preparing Hamiltonians as inputs for quantum computers. In this paper, we study how to use quantum computing to solve BP problems. However, due to limited hardware resources, existing quantum computers are unable to tackle large optimization spaces. Therefore, we propose an efficient Hamiltonian Reduction method that allows quantum processors to solve large BP instances encountered in LEO systems. We conduct our simulations on real quantum computers (D-Wave Advantage) using a real dataset of vessel locations in the US. Numerical results show that our algorithm outperforms commercialized solutions of D-Wave by allowing existing quantum annealers to solve 17.5 times larger BP instances while maintaining high solution quality. Although quantum computing cannot theoretically overcome the hardness of BP problems, this work contributes early efforts to applying quantum computing in satellite optimization problems, especially applications formulated as clique cover/graph coloring problems.

Private Information Retrieval (PIR) schemes allow a client to retrieve any file of interest, while hiding the file identity from the database servers. In contrast to most existing PIR schemes that assume honest-but-curious servers, we study the case of dishonest servers. The latter provide incorrect answers and try to persuade the client to output the wrong result. We introduce several PIR schemes with information-theoretic privacy and result verification for the case of two servers. Security guarantees can be information-theoretical or computational, and the verification keys can be public or private. In this work, our main performance metric is the download rate.

We consider the problem of designing a Private Information Retrieval (PIR) scheme on m files replicated on k servers that can collude or, even worse, can return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We consider the asymptotic information-theoretic capacity of this problem defined as the maximum ratio of the number of correctly retrieved symbols to the downloaded one for a large enough number of stored files. We propose an achievable scheme with a small file size and prove that such a file size is minimal for the fixed number of retrieved symbols, solving the problem pointed out by Banawan and Ulukus.A full version [1] of this paper is accessible at: https://arxiv.org/abs/2302.02230

Motivated by the application of Reed-Solomon codes to recently emerging decentralized storage systems such as Storj and Filebase/Sia, we study the problem of designing compact repair groups for recovering multiple failures in a decentralized manner. Here, compactness means that the corresponding trace repair schemes of these groups of helpers can be generated from a single or a few seed repair schemes, thus saving the time and space required for finding and storing them. The goal is to design compact repair groups that can tolerate as many failures as possible. It turns out that the maximum number of failures a collection of repair groups can tolerate equals the size of a minimum hitting set of a collection of subsets of the finite field ${\mathbb{F}_{{q^\ell }}}$ minus one. When the repair groups for each symbol are generated from a single subspace, we establish a pair of asymptotically tight lower bound and upper bound on the size of such a minimum hitting set. Using Burnside’s Lemma and the Möbius inversion formula, we determine a number of subspaces that together attain the upper bound on the minimum hitting set size when the repair groups are generated from multiple subspaces.

Distributed computing, in which a resource-intensive task is divided into subtasks and distributed among different machines, plays a key role in solving large-scale problems.Coded computingis a recently emerging paradigm where redundancy for distributed computing is introduced to alleviate the impact of slow machines (stragglers) on the completion time. We investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. This is motivated by recently available services in the cloud computing industry (e.g., EC2 Spot, Azure Batch) where low-priority virtual machines are offered at a fraction of the price of the on- demand instances but can be preempted on short notice. Our contributions are three-fold. We first introduce a new concept calledtransition wastethat quantifies the number of tasks existing machines must abandon or take over when a machine joins/leaves. We then develop an efficient method to minimize the transition waste for the cyclic task allocation scheme recently proposed in the literature (Yang et al. ISIT’19). Finally, we establish a novel solution based on finite geometry achievingzerotransition wastes given that the number of active machines varies within a fixed range.

Minimum weight codewords play a crucial role in the error correction performance of a linear block code. In this work, we establish an explicit construction for these codewords of polar codes as a sum of the generator matrix rows, which can then be used as a foundation for two applications. In the first application, we obtain a lower bound for the number of minimum-weight codewords (a.k.a. the error coefficient), which matches the exact number established previously in the literature. In the second application, we derive a novel method that modifies the information set (a.k.a. rate profile) of polar codes and PAC codes in order to reduce the error coefficient, hence improving their performance. More specifically, by analyzing the structure of minimum-weight codewords of polar codes (as special sums of the rows in the polar transform matrix), we can identify rows (corresponding to information bits) that contribute the most to the formation of such codewords and then replace them with other rows (corresponding to frozen bits) that bring in few minimum-weight codewords. A similar process can also be applied to PAC codes. Our approach deviates from the traditional constructions of polar codes, which mostly focus on the reliability of the sub-channels, by taking into account another important factor - the weight distribution. Extensive numerical results show that the modified codes outperform PAC codes and CRC-Polar codes at the practical block error rate of$10^{-2}$-$10^{-3}$.

The issue of repairing Reed-Solomon codes currently employed in industry has been sporadically discussed in the literature. In this work we carry out a systematic study of these codes and investigate important aspects of repairing them under the trace repair framework, including which evaluation points to select and how to implement a trace repair scheme efficiently. In particular, we employ different heuristic algorithms to search for low-bandwidth repair schemes for codes of short lengths with typical redundancies and establish three tables of current best repair schemes for [n, k] Reed-Solomon codes over GF(256) with 4 ≤ n ≤ 16 and r = n − k ∈ {2, 3, 4}. The tables cover most known codes currently used in the distributed storage industry.

Polar codes are normally constructed based on the reliability of the sub-channels in the polarized vector channel. Code construction based on reliability is compatible with successive cancellation decoding. However, due to poor Hamming distance properties, the designed codes cannot perform well with near maximum likelihood decoders. In this work, we propose a new approach that modifies polar codes and PAC codes to significantly lower the number of codewords with minimum distance (a.k.a. error coefficient). This approach is based on the recognition of all the rows of polar transform involved in the formation of the minimum-weight codewords. The numerical results show that the designed codes outperform polar codes and PAC codes under list decoding.

We propose new repair schemes for Reed-Solomon codes that use subspace polynomials and hence generalize previous works in the literature that employ trace polynomials. The Reed-Solomon codes are over \mathbb Fqland have redundancy r = n-k ≥ qm, 1 ≤ m ≤l, where n and k are the code length and dimension, respectively. In particular, for one erasure, we show that our schemes can achieve optimal repair bandwidths whenever n=qland r = qm, for all 1 ≤ m ≤l. For two erasures, our schemes use the same bandwidth per erasure as the single erasure schemes, forl/m is a power of q, and forl= qa, m=qb-1 > 1 ( a ≥ b ≥ 1), and for m ≥l/2 whenlis even and q is a power of two.

Motivated by recently available services in the cloud computing industry, e.g., EC2 Spot or Azure Batch, where spare/low-priority virtual machines are offered at a fraction of the price of the on-demand instances but can be preempted on short notice, we investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. Our contributions are two-fold: We first propose an efficient method to minimize the transition waste, a newly introduced concept quantifying the total number of tasks that existing machines have to abandon or take on anew when a machine joins or leaves, for the cyclic elastic task allocation scheme recently proposed in the literature (Yang et al. ISIT'19). We then proceed to generalize such a scheme and introduce new task allocation schemes based on finite geometry that achieve zero transition wastes as long as the number of active machines varies within a fixed range. The proposed solutions can be applied on top of existing coded computing schemes tolerating stragglers.

Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial \(S(t,t+1,v)\) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v , there is a Steiner triple system ( S (2, 3, v )) whose largest difference in block sums is within an additive constant of the lower bound.

We address the new problem of designing large families of subsets of a common labeled ground set that simultaneously have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the subsets is less than or equal to one. Our results include an upper bound on the size of such families, and constructions based on transversal designs, packings, and new forms of Latin rectangles. The constructions jointly optimize the size of the family of sets and the labeling scheme and achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The intersecting sets discrepancy problem is motivated by emerging applications in coding for molecular data storage.

We design p-reconstructible μ-secure [n, k] erasure coding schemes (0 ≤ μ3/4.

An index code for broadcast channel with receiver side information is locally decodable if each receiver can decode its demand by observing only a subset of the transmitted codeword symbols instead of the entire codeword. Local decodability in index coding is known to reduce receiver complexity, improve user privacy and decrease decoding error probability in wireless fading channels. Conventional index coding solutions assume that the receivers observe the entire codeword, and as a result, for these codes the number of codeword symbols queried by a user per decoded message symbol, which we refer to as locality, could be large. In this paper, we pose the index coding problem as that of minimizing the broadcast rate for a given value of locality (or vice versa) and designing codes that achieve the optimal trade-off between locality and rate. We identify the optimal broadcast rate corresponding to the minimum possible value of locality for all single unicast problems. We present new structural properties of index codes which allow us to characterize the optimal trade-off achieved by: vector linear codes when the side information graph is a directed cycle; and scalar linear codes when the minrank of the side information graph is one less than the order of the problem. We also identify the optimal trade-off among all codes, including non-linear codes, when the side information graph is a directed 3-cycle. Finally, we present techniques to design locally decodable index codes for arbitrary single unicast problems and arbitrary values of locality.

An index code is said to be locally decodable if each receiver can decode its demand using its side information and by querying only a subset of the transmitted codeword symbols instead of observing the entire codeword. Local decodability can be a beneficial feature in some communication scenarios, such as when the receivers can afford to listen to only a part of the transmissions because of limited availability of power. The locality of an index code is the ratio of the maximum number of codeword symbols queried by a receiver to the message length. In this paper we analyze the optimum locality of linear codes for the family of index coding problems whose min-rank is one less than the number of receivers in the network. We first derive the optimal trade-off between the index coding rate and locality with vector linear coding when the side information graph is a directed cycle. We then provide the optimal trade-off achieved by scalar linear coding for a larger family of problems, viz. problems where the min-rank is only one less than the number of receivers. While the arguments used for achievability are based on known coding techniques, the converse arguments rely on new results on the structure of locally decodable index codes.

We are concerned with the problem of designing large families of subsets over a common labeled ground set that have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the sets is less than or equal to one. Our results, based on transversal designs, factorizations of packings and Latin rectangles, show that by jointly constructing the sets and labeling scheme, one can achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The design problem considered is motivated by applications in molecular data storage.

Minimizing the repair bandwidth, i.e., the amount of information from the helper nodes needed for recovering the content of one failed node in an erasure-coded distributed storage system, has been the focus of many works in the literature. We investigate another important performance metric, namely the I/O cost, which specifies the amount of information that needs to be read by the helper nodes during the repair process of one failed node. We analyze the I/O costs of a few known repair schemes for Reed-Solomon codes of various lengths, in contrast to the previous works in this direction, which only studied the I/O costs in repairing full-length Reed-Solomon codes.

A novel iterative approach for soft-decision decoding of Reed-Solomon codes is presented that employs symbol-level belief propagation on an alternative parity-check matrix representation of the code. Construction of a suitable matrix is discussed from the viewpoint of iterative decoding, and certain conditions are derived on existence of structures detrimental for decoding. Simulation results demonstrate that the novel scheme performs substantially better than hard-decision decoding, especially with high rate codes, while being of much lower complexity than existing soft-decision decoding methods. Proposed method is also well-suited for efficient hardware implementations.

We study the problem of constructing balanced generator matrices for Reed-Solomon and Tamo-Barg codes. More specifically, we are interested in realizing generator matrices, for the full-length cyclic versions of these codes, where all rows have the same weight and the difference in weight between any columns is at most one. The results presented in this paper translate to computationally balanced encoding schemes, which can be appealing in distributed storage applications. Indeed, the balancedness of these generator matrices guarantees that the computation effort exerted by any storage node is essentially the same. In general, the framework presented can accommodate various values for the required row weight. We emphasize the possibility of constructing sparsest and balanced generator matrices for Reed-Solomon codes, i.e., each row is a minimum distance codeword. The number of storage nodes contacted once a message symbol is updated decreases with the row weight, so sparse constructions are appealing in that context. Results of similar flavor are presented for cyclic Tamo-Barg codes. In particular, we show that for a code with minimum distance d and locality r, a construction in which every row is of weight d+r-1 is possible. The constructions presented are deterministic and operate over the codes' original underlying finite field. As a result, efficient decoding from both errors and erasures is possible thanks to the plethora of efficient decoders available for the codes considered.

Network transfer and disk read are the most time consuming operations in the repair process for node failures in erasure-code-based distributed storage systems. Recent developments on Reed-Solomon codes, the most widely used erasure codes in practical storage systems, have shown that efficient repair schemes specifically tailored to these codes can significantly reduce the network bandwidth spent to recover single failures. However, the I/O cost, that is, the number of disk reads performed in these repair schemes remains largely unknown. We take the first step to address this gap in the literature by investigating the I/O costs of some existing repair schemes for full-length Reed-Solomon codes.

Network transfer and disk read constitute the two most time-consuming operations in the repair process for node failures in erasure-code-based distributed storage systems. Recent developments on Reed-Solomon codes have demonstrated repair schemes that achieve optimal network bandwidths in the recovery of single failures, although in certain cases at the expense of a trivially high I/O cost, a term referring to the number of disk reads performed in a repair scheme. We are interested in the lowest I/O cost a repair scheme can achieve for Reed-Solomon codes. We establish two repair schemes for a family of Reed-Solomon codes with two parities that achieve the optimal I/O cost.

Many code families such as low-density parity-check codes, fractional repetition codes, batch codes, and private information retrieval codes with low storage overhead rely on the use of combinatorial block designs or derivatives thereof. In the context of distributed storage applications, one is often faced with system design issues that impose additional constraints on the coding schemes and therefore on the underlying block designs. Here, we address one such problem, pertaining to server access frequency balancing, by introducing a new form of Steiner systems, termed MaxMinSum Steiner systems. MaxMinSum Steiner systems are characterized by the property that the minimum value of the sum of points (elements) within a block is maximized or that the minimum sum of block indices containing some fixed point is maximized. We show that proper relabelings of points in the Bose and Skolem constructions for Steiner triple systems lead to optimal MaxMin values for the sums of interest; for the duals of the designs, we exhibit block labelings that are within a $3/4$ multiplicative factor from the optimum.

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.

Motivated by applications in social network community analysis, we introduce a new clustering paradigm termed motif clustering. Unlike classical clustering, motif clustering aims to minimize the number of clustering errors associated with both edges and certain higher order graph structures (motifs) that represent “atomic units” of social organizations. Our contributions are two-fold: We first introduce motif correlation clustering, in which the goal is to agnostically partition the vertices of a weighted complete graph so that certain predetermined “important” social subgraphs mostly lie within the same cluster, while “less relevant” social subgraphs are allowed to lie across clusters. We then proceed to introduce the notion of motif covers, in which the goal is to cover the vertices of motifs via the smallest number of (near) cliques in the graph. Motif cover algorithms provide a natural solution for overlapping clustering and they also play an important role in latent feature inference of networks. For both motif correlation clustering and its extension introduced via the covering problem, we provide hardness results, algorithmic solutions and community detection results for two well-studied social networks.

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. We extend their trace collection technique to cope with two erasures.

Reed-Solomon codes have found many applications in practical storage systems, but were until recently considered unsuitable for distributed storage applications due to the widely-held belief that they have poor repair bandwidth. The work of Guruswami and Wootters (STOC'16) has shown that one can actually perform bandwidth-efficient linear repair with Reed-Solomon codes: When the codes are over the field Fqt and the number of parities r ≥ qs, where (t - s) divides t, there exists a linear scheme that achieves a repair bandwidth of (n - 1)(t - s) logg q bits. We extend this result by showing the existence of such a linear repair scheme for every 1 ≤ stand r = qs. Additionally, we improve the lower bound on the repair bandwidth for Reed-Solomon codes, also established in the work of Guruswami and Wootters.

We construct balanced and sparse generator matrices for Tamo and Barg's Locally Recoverable Codes (LRCs). More specifically, for a cyclic Tamo-Barg code of length n, dimension k and locality r, we show how to deterministically construct a generator matrix where the number of nonzeros in any two columns differs by at most one, and where the weight of every row is d + r - 1, where d is the minimum distance of the code. Since LRCs are designed mainly for distributed storage systems, the results presented in this work provide a computationally balanced and efficient encoding scheme for these codes. The balanced property ensures that the computational effort exerted by any storage node is essentially the same, whilst the sparse property ensures that this effort is minimal. The work presented in this paper extends a similar result previously established for Reed-Solomon (RS) codes, where it is now known that any cyclic RS code possesses a generator matrix that is balanced as described, but is sparsest, meaning that each row has d nonzeros.

We propose a new latent Boolean feature model for complex networks that capture different types of node interactions and network communities. The model is based on a new concept in graph theory, termed the Boolean intersection representation of a graph, which generalizes the notion of an intersection representation. We mostly focus on one form of Boolean intersection, termed cointersection, and describe how to use this representation to deduce node feature sets and their communities. We derive several general bounds on the minimum number of features used in cointersection representations and discuss graph families for which exact cointersection characterizations are possible. Our results also include algorithms for finding optimal and approximate cointersection representations of a graph.

We propose a new latent Boolean feature model for complex networks that captures different types of node interactions and network communities. The model is based on a new concept in graph theory, termed the co-intersection representation of a graph, which generalizes the notion of an intersection representation. We describe how to use co-intersection representations to deduce node feature sets and their communities, and proceed to derive several general bounds on the minimum number of features used in co-intersection representations. We also discuss graph families for which exact co-intersection characterizations are possible, and describe algorithms for computing co-intersection numbers and assignments.

We consider the locality of encoding and decoding operations in distributed storage systems (DSS), and propose a new class of codes, called locally encodable and decodable codes (LEDC), that provides a higher degree of operational locality compared to currently known codes. For a given locality structure, we derive an upper bound on the global distance and demonstrate the existence of an optimal LEDC for sufficiently large field size. In addition, we also construct two families of optimal LEDC for fields with size linear in code length.

The MDS property (aka the k-out-of-n property) requires that if a file is split into several symbols and subsequently encoded into n coded symbols, each being stored in one storage node of a distributed storage system (DSS), then an user can recover the file by accessing any k nodes. We study the so-called p-decodable μ-secure erasure coding scheme (1 ≤ p ≤ k - μ, 0 ≤ μ <; k, p|(k - μ)), which satisfies the MDS property and the following additional properties: (P1) strongly secure up to a threshold: an adversary which eavesdrops at most μ storage nodes gains no information (in Shannon's sense) about the stored file, (P2) partially decodable: a legitimate user can recover a subset of p file symbols by accessing some μ + p storage nodes. (P2) partially decodable: a legitimate user can recover a subset of p file symbols by accessing some μ + p storage nodes. The scheme is perfectly p-decodable μ-secure if it satisfies the following additional property: (P3) weakly secure up to a threshold: an adversary which eavesdrops more than μ but less than μ + p storage nodes cannot reconstruct any part of the file. Most of the related work in the literature only focused on the case p = k - μ. In other words, no partial decodability is provided: an user cannot retrieve any part of the file by accessing less than k nodes. For our more general code, Property (P2) guarantees partial decodability: once the user accesses p more nodes than the strong security threshold μ, it can start to decode some subset of p file symbols. We provide an explicit construction of p-decodable μ-secure coding schemes over small fields for all μ and p. That construction also produces perfect p-decodable μ-secure schemes over small fields when p = 1 (for every μ), and when μ = 0, 1 (for every p). We establish that perfect schemes exist over sufficiently large fields for almost all μ and p.

We consider a simple multiple access network (SMAN), where k sources of unit rates transmit their data to a common sink via n relays. Each relay is connected to the sink and to certain sources. A coding scheme (for the relays) is weakly secure if a passive adversary who eavesdrops on less than k relay-sink links cannot reconstruct the data from each source. We show that there exists a weakly secure maximum distance separable (MDS) coding scheme for the relays if and only if every subset of ℓ relays must be collectively connected to at least ℓ+1 sources, for all 0 <; ℓ <; k. Moreover, we prove that this condition can be verified in polynomial time in n and k. Finally, given a SMAN satisfying the aforementioned condition, we provide another polynomial time algorithm to trim the network until it has a sparsest set of source-relay links that still supports a weakly secure MDS coding scheme.

We investigate a simple multiple access network (SMAN) where k independent sources of unit rates multicast their information to a set of sinks, via n commonly shared relays. All links are assumed to have unit capacity. Given such a SMAN, a coding scheme for the relays is called optimal if each sink can retrieve all information from the sources under at most ⌊n-k+1/2⌋ node/link errors. We study the problem of designing the sparsest SMAN, i.e., the SMAN that has the least number of edges, that supports an optimal coding scheme for the relays. Additionally, the SMAN must satisfy either of the following constraints: 1) Connection Constraint: Each relay can be connected only to a given subset of sources or 2) Balance Constraint: Each relay must be connected to approximately the same number of sources. We provide two polynomial time algorithms to identify the cases where such a SMAN exists together with its optimal coding scheme designed over sufficiently large fields. One algorithm is based on a nontrivial modification of the well-known Gale-Ryser algorithm, whereas the other is based on a novel generalization of the famous Hall's marriage theorem. We also propose a combinatorial approach to construct optimal coding schemes over small fields and settle the problem for a special case.

We study the Relay-based Cooperative Data Exchange (RCDE) problem, where initially each client has access to a subset of a set of n original packets, referred to as their side information, and wants to retrieve all other original packets via cooperation. Unlike traditional Cooperative Data Exchange (CDE), in our proposed relay-based model, clients can only cooperate via a relay. The data exchange is completed over two phases, namely Uploading Phase and Downloading Phase. In the Uploading Phase, the clients will encode the original packets and transmit the coded packets to the relay. In the Downloading Phase, the relay will reencode the received packets and multicast the reencoded packets, each to a subgroup of clients. The coded packets in the two phases are carefully selected so that each client can retrieve all n original packets with minimum total transmission delay, based on its initial side information and on the coded packets it receives from the relay. In addition, we assume that the bandwidths between the relay and different clients are different, and that the upload/download bandwidths between the relay and the same client are also different. We establish a coding scheme that has the minimum total delay and show that it can be found in polynomial time, for sufficiently large underlying fields. We also design a heuristic algorithm that has a low complexity with binary field size. Our simulations show that the performance of the binary solution is very close to that of the optimal solution. All coding schemes considered in this work are scalar.

Parity declustering allows faster reconstruction of a disk array when some disk fails. Moreover, it guarantees uniform reconstruction workload on all surviving disks. It has been shown that parity declustering for one-failure tolerant array codes can be obtained via Balanced Incomplete Block Designs. We extend this technique for array codes that can tolerate an arbitrary number of disk failures via t-designs.

We study the existence over small fields of Maximum Distance Separable (MDS) codes with generator matrices having specified supports (i.e. having specified locations of zero entries). This problem unifies and simplifies the problems posed in recent works of Yan and Sprintson (NetCod'13) on weakly secure cooperative data exchange, of Halbawi et al. (arxiv'13) on distributed Reed-Solomon codes for simple multiple access networks, and of Dau et al. (ISIT'13) on MDS codes with balanced and sparse generator matrices.We conjecture that there exist such [n, k]qMDS codes as long as q ≥ n + k - 1, if the specified supports of the generator matrices satisfy the so-called MDS condition, which can be verified in polynomial time. We propose a combinatorial approach to tackle the conjecture, and prove that the conjecture holds for a special case when the sets of zero coordinates of rows of the generator matrix share with each other (pairwise) at most one common element. Based on our numerical result, the conjecture is also verified for all k ≤ 7. Our approach is based on a novel generalization of the well-known Hall's marriage theorem, which allows (overlapping) multiple representatives instead of a single representative for each subset.

A passive adversary can eavesdrop stored content or downloaded content of some storage nodes, in order to learn illegally about the file stored across a distributed storage system (DSS). Previous work in the literature focuses on code constructions that trade storage capacity for perfect security. In other words, by decreasing the amount of original data that it can store, the system can guarantee that the adversary, which eavesdrops up to a certain number of storage nodes, obtains no information (in Shannon's sense) about the original data. In this work we introduce the concept of block security for DSS and investigate minimum bandwidth regenerating (MBR) codes that are block secure against adversaries of varied eavesdropping strengths. Such MBR codes guarantee that no information about any group of original data units up to a certain size is revealed, without sacrificing the storage capacity of the system. The size of such secure groups varies according to the number of nodes that the adversary can eavesdrop. We show that code constructions based on Cauchy matrices provide block security. The opposite conclusion is drawn for codes based on Vandermonde matrices.

Linear erasure codes with local repairability are desirable for distributed data storage systems. An [n, k, d] linear code having all-symbol (r, δ)-locality, denoted as (r, δ)a, is considered optimal if it has the actual highest minimum distance of any code of the given parameters n, k, r and δ. A minimum distance bound is given in [10]. The existing results on the existence and the construction of optimal (r, δ)alinear codes are limited to only two small regions within this special case, namely, i) m = 0 and ii) m ≥ (v+δ-1) > (δ-1) and δ = 2, where m = n mod (r+δ-1) and v = k mod r. This paper investigates the properties and existence conditions for optimal (r, δ)alinear codes with general r and δ. First, a structure theorem is derived for general optimal (r, δ)acodes which helps illuminate some of their structure properties. Next, the entire problem space with arbitrary n, k, r and δ is divided into eight different cases (regions) with regard to the specific relations of these parameters. For two cases, it is rigorously proved that no (r, δ)alinear code can achieve the minimum distance bound in [10]. For four other cases the optimal (r, δ)acodes are shown to exist over a field of size q ≥ (k-1n), deterministic constructions are proposed. Our new constructive algorithms not only cover more cases, but for the same cases where previous algorithms exist, the new constructions require a smaller field, which translates to potentially lower computational complexity. Our findings substantially enriches the knowledge on optimal (r, δ)alinear codes, leaving only two cases in which the construction of optimal codes are not yet known.

The min-rank of a digraph was shown to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this paper, the graphs and digraphs of near-extreme min-ranks are studied. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. In addition, a circuit-packing bound is revisited, and several families of digraphs, optimal with respect to this bound, whose min-ranks can be found in polynomial time, are presented.

We show that given n and k, for q sufficiently large, there always exists an [n, k]qMDS code that has a generator matrix G satisfying the following two conditions: (C1) Sparsest: each row of G has Hamming weight n - k + 1; (C2) Balanced: Hamming weights of the columns of G differ from each other by at most one.

In this paper, we consider the problem of minimizing the delay for data exchange among a group of wireless clients, where each client initially holds a subset of the packets and needs to get all the packets held by other clients. It is assumed that clients cannot communicate with each another directly, they can only exchange packets through a wireless relay. To minimize the total transmission delay during data exchange process, we need to determine at every client, which packets to be uploaded and how to encode the packets. It is also important for the relay node to decide how to encode multiple packets from different clients and select the transmission rate in the downloading process, such that every client can decode all required packets in shortest delay. We first formulate theoretically the above problem of minimizing the total transmission delay as an integer programming, and show that its complexity is NP hard. We then propose an efficient heuristic algorithm, which consists of two processes: uploading process, i.e., how to select and encode the packets from the clients to the relay, and downloading process, i.e., how the relay encode packets and select transmission rate for broadcast to all clients. For each process, theoretical formulation has been derived to minimize their transmission delay, and efficient algorithms are proposed separately. Finally, simulation results demonstrate the effectiveness of the proposed algorithm in reducing the total data exchange delay.

In this paper, we dynamically select the transmission rates to reduce the transmission delay required for network coded cooperative data exchange. With low transmission rate, more clients can receive the packet due to longer transmission range. However, low transmission rate may incur extra transmission delay. We consider a delay minimization with rate selection and network coding (DMRSNC) for cooperative data exchange problem under two cases: with and without packet splitting. We construct a network information flow graph to model such a problem, and design transmission strategy with the aim of minimizing transmission delay. With packet splitting, the DMRSNC problem can be formulated as a linear programming based on the graph model, which can be solved in polynomial time. When the packet splitting is not allowed, we derive an upper bound for the minimum total transmission delay required for DMRSNC problem. In addition, we derive that the upper bound is at most three times of the optimal solution in a special case. Finally, the simulation results demonstrate the superiority of the proposed scheme in reducing the total transmission delay.

A problem of index coding with side information was first considered by Birk and Kol in 1998. In this study, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols δ , what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the α-bound and the κ -bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with a maximum distance separable classical code is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Further, the problem of error-correcting decoding by a linear ECIC is studied. It is shown that in order to decode correctly the desired symbol, the decoder is required to find one of the vectors, belonging to an affine space containing the actual error vector. The syndrome decoding is shown to produce the correct output if the weight of the error pattern is less or equal to the error-correcting capability of the corresponding ECIC. Finally, the notion of static ECIC, which is suitable for use with a family of instances of an index coding problem, is introduced. Several bounds on the length of static ECICs are derived, and constructions for static ECICs are discussed. Connections of these codes to weakly resilient Boolean functions are established.

The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. It is also shown that the decision problem of whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time.

Security aspects of the index coding with side information (ICSI) problem are investigated. Building on the results of Bar-Yossef (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrixL, whose column space codeC(L) has lengthn, minimum distanced, and dual distanced⊥, is (d-1-t) -block secure (and hence also weakly secure) if the adversary knows in advancet≤d-2 messages, and is completely insecure if the adversary knows in advance more thann-d⊥messages. Strong security is examined under the conditions that the adversary: 1) possessestmessages in advance; 2) eavesdrops at most μ transmissions; 3) corrupts at most δ transmissions. We prove that for sufficiently largeq, an optimal linear index code which is strongly secure against such an adversary has length κq+μ+2δ . Here, κqis a generalization of the min-rank over Fqof the side information graph for the ICSI problem in its original formulation in the work of Bar-Yossef et al.

Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrix L, whose column space code C(L) has length n, minimum distance d and dual distance d⊥, is (d-1-t)-block secure (and hence also weakly secure) if the adversary knows in advance t ≤ d - 2 messages, and is completely insecure if the adversary knows in advance more than n-d⊥messages. Strong security is examined under the conditions that the adversary: (i) possesses t messages in advance; (ii) eavesdrops at most μ transmissions; (iii) corrupts at most δ transmissions. We prove that for sufficiently large q, an optimal linear index code, which is strongly secure against such an adversary, has length κq+μ+2δ. Here κqis a generalization of the min-rank over Fqof the side information graph for the ICSI problem in its original formulation in the work of Bar-Yossef et al.

A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols δ, what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest-length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the α-bound and the κ-bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with an MDS classical code, is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Finally, the decoding of linear ECIC's is discussed. The syndrome decoding is shown to output the exact message if the weight of the error vector is less or equal to the error-correcting capability of the corresponding ECIC.

An optimal constant-composition or constant-weight code of weight $w$ has linear size if and only if its distance $d$ is at least $2w-1$. When $d\geq 2w$, the determination of the exact size of such a constant-composition or constant-weight code is trivial, but the case of $d=2w-1$ has been solved previously only for binary and ternary constant-composition and constant-weight codes, and for some sporadic instances. This paper provides a construction for quasicyclic optimal constant-composition and constant-weight codes of weight $w$ and distance $2w-1$ based on a new generalization of difference triangle sets. As a result, the sizes of optimal constant-composition codes and optimal constant-weight codes of weight $w$ and distance $2w-1$ are determined for all such codes of sufficiently large lengths. This solves an open problem of Etzion. The sizes of optimal constant-composition codes of weight $w$ and distance $2w-1$ are also determined for all $w\leq 6$, except in two cases.

This correspondence introduces two new constructive techniques to complete the determination of the sizes of optimal$q$-ary codes of constant weight three and distance four.