A General Construction for PMDS Codes Calis, Gokhan; Koyluoglu, O. Ozan
IEEE communications letters,
2017-March, 2017-3-00, Letnik:
21, Številka:
3
Journal Article
Recenzirano
Odprti dostop
Partial MDS (PMDS) also known as maximally recoverable codes allow for local erasure recovery by utilizing row-wise parities and additional erasure correction through global parities. Recent works on ...PMDS codes focus on special case parameter settings, and a general construction for PMDS codes is stated as an open problem. This letter provides an explicit construction for PMDS codes for all parameters utilizing concatenation of Gabidulin and MDS codes, a technique originally proposed by Rawat et al. for constructing optimal locally repairable codes. This approach allows for PMDS constructions for any parameters albeit with large field sizes. To lower the field size, a relaxation on the rate requirement is considered, and PMDS codes based on combinatorial designs are constructed.
In this paper, we observe the possibility that the group \(S_{n}\times S_{m}\) acts as a flag-transitive automorphism group of a block design with point set \(\{1,\ldots ,n\}\times \{1,\ldots ...,m\},4\leq n\leq m\leq 70\). We prove the equivalence of that problem to the existence of an appropriately defined smaller flag-transitive incidence structure. By developing and applying several algorithms for the construction of the latter structure, we manage to solve the existence problem for the desired designs with \(nm\) points in the given range. In the vast majority of the cases with confirmed existence, we obtain all possible structures up to isomorphism.
Gyárfás famously showed that in every r-coloring of the edges of the complete graph Kn, there is a monochromatic connected component with at least nr−1 vertices. A recent line of study by Conlon, ...Tyomkyn, and the second author addresses the analogous question about monochromatic connected components with many edges. In this paper, we study a generalization of these questions for k-uniform hypergraphs. Over a wide range of extensions of the definition of connectivity to higher uniformities, we provide both upper and lower bounds for the size of the largest monochromatic component that are tight up to a factor of 1+o(1) as the number of colors grows. We further generalize these questions to ask about counts of vertex s-sets contained within the edges of large monochromatic components. We conclude with more precise results in the particular case of two colors.
The n-queens problem is to determine Q(n), the number of ways to place n mutually non-threatening queens on an n×n board. We show that there exists a constant α=1.942±3×10−3 such that ...Q(n)=((1±o(1))ne−α)n. The constant α is characterized as the solution to a convex optimization problem in P(−1/2,1/22), the space of Borel probability measures on the square.
The chief innovation is the introduction of limit objects for n-queens configurations, which we call queenons. These form a convex set in P(−1/2,1/22). We define an entropy function that counts the number of n-queens configurations that approximate a given queenon. The upper bound uses the entropy method of Radhakrishnan and Linial–Luria. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queenon and whose entropy matches that found in the upper bound. The enumeration of n-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons.
Along the way we prove a large deviations principle for n-queens configurations that can be used to study their typical structure.
Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs via a table-based repair model. For a given file size, it is desirable to ...design FR codes that minimize the reconstruction degree, which is defined as the number of storage nodes required for data retrieval. In this paper, we first consider a lower bound on the reconstruction degree of FR codes obtained by Silberstein and Etzion. We present several families of FR codes that attain this lower bound, which are derived from combinatorial designs and regular graphs. We further provide a new lower bound on the reconstruction degree of FR codes, which is tighter than the existing one. Moreover, we show that for an FR code with reconstruction degree achieving the lower bounds, the corresponding dual code attains upper bounds on the supported file size.
Fractional repetition (FR) codes are a class of repair efficient erasure codes that can recover a failed storage node with both optimal repair bandwidth and complexity. In this paper, we study the ...minimum distance of FR codes, which is the smallest number of nodes whose failure leads to the unrecoverable loss of the stored file. We derive a new upper bound on the minimum distance of FR codes, which is tighter than the Singleton bound and a Singleton-like bound that takes locality into account. Based on regular graphs and combinatorial designs, several families of FR codes with optimal minimum distance are obtained.
The compatibility between craftsmanship and industrial product design is an important axis of modern design development. This research seeks to integrate the craft process and industrial product ...design methodology to achieve mass production while maintaining characteristics of traditional craftsmanship. This study constructs an operational model to formulate appropriate strategies, present two craft cases, and utilize the triangulation method to explore synergistic effects between craft process and industrial product design. The conclusions reveal that craft materials, modules, innovation, and living technology are four key design features of the modern craft model. Moreover, this study proposes a new craft development model which applies the module concept to determine feasible market strategies that can be implemented to bridge the gap between craft and product design processes. Importantly, this study also draws upon theories and models proposed by previous researchers to explain how modern craftsmanship can be leveraged to establish market niches for mass-produced products. The concept of modern crafts facilitates cross-domain collaboration and integration, contributes to the field of traditional crafts and product design, and creates niche markets for traditional craft products. This novel approach can therefore be leveraged to advance the development of sustainable design, innovative material use, product recycling, innovative design concepts, and human-friendly design.
•How to integrate the craft process and industrial product design methodology?•A conceptual framework for achieving modern craft design is developed.•Conceptual recombination mixed with traditional materials is a driver of innovation.•Focus on sustainable design, innovative material use, and human-friendly design.
We prove that (1): the characteristic function of each independent set in each regular graph attaining the Delsarte–Hoffman bound is a perfect coloring; (2): each transversal in a uniform regular ...hypergraph is an independent set in the vertex adjacency multigraph of a hypergraph attaining the Delsarte–Hoffman bound for this multigraph; and (3): the combinatorial designs with parameters
-
and their
-analogs, difference sets, Hadamard matrices, and bent functions are equivalent to perfect colorings of some graphs of multigraphs, in particular, the Johnson graph
for
-
-designs and the Grassmann graph
for bent functions.
Network switches and routers scale in rate by distributing the packet read/write operations across multiple memory banks. Rate scaling is achieved so long as sufficiently many packets can be written ...and read in parallel. However, due to the non-determinism of the read process, parallel pending read requests may contend on memory banks, and thus significantly lower the switching rate. In this paper, we provide a constructive study of codes that guarantee fully parallel data reconstruction without contention. We call these codes "switch codes," and construct three optimal switch-code families with different parameters. All the constructions use only simple XOR-based encoding and decoding operations, an important advantage when operated in ultra-high speeds. Switch codes achieve their good performance by spanning simultaneous disjoint local-decoding sets for all their information symbols. Switch codes may be regarded as an extreme version of the previously studied batch codes, where the switch version requires parallel reconstruction of all the information symbols.
PDF
