Binary tree gray codes

In this paper the problem of generating all binary trees, as represented by well-formed parentheses strings, in such a way that the changes in successively generated trees are constant is discussed. In particular, an algorithm is developed that generates the strings by simply interchanging a left and a right parenthesis. It is also proven that it is impossible to generate all trees by interchanging an adjacent left and right (or right and left) parenthesis pair. The Appendix contains a Pascal program that implements the generation algorithm. Also, ranking and unranking algorithms are given.     

Robust locally testable codes and products of codes

We continue the investigation of locally testable codes, i.e., error‐correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically checkable proofs, we introduce the notion of robust local testability of codes. We relate this notion to a product of codes introduced by Tanner and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low‐degree multivariate polynomials (which are a special case of tensor codes). Combining these two results gives us a generic construction of codes of inverse polynomial rate that are testable with poly‐logarithmically many queries. We note that these locally testable tensor codes can be obtained from any linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Generalized balanced tournament designs and related codes

A generalized balanced tournament design, or a GBTD(k, m) in short, is a (km, k, k − 1)-BIBD defined on a km-set V. Its blocks can be arranged into an m × (km − 1) array in such a way that (1) every element of V is contained in exactly one cell of each column, and (2) every element of V is contained in at most k cells of each row. In this paper, we present a new construction for GBTDs and show that a GBTD(4, m) exists for any integer m ≥ 5 with at most eight possible exceptions. A link between a GBTD(k, m) and a near constant composition code is also mentioned. The derived code is optimal in the sense of its size.      

Blowing-up points on locally conformally balanced manifolds

In this note, we show that the blowing-up of a point on a locally conformally balanced manifold also admits a locally conformally Balanced manifold structure.     

Lower bounds for adaptive locally decodable codes

An error‐correcting code is said to be locally decodable if a randomized algorithm can recover any single bit of a message by reading only a small number of symbols of a possibly corrupted encoding of the message. Katz and Trevisan 12 showed that any such code C : {0, 1}ⁿ → Σ^m with a decoding algorithm that makes at most q probes must satisfy m = Ω((n/log |Σ|)^q/(q?1)). They assumed that the decoding algorithm is non‐adaptive, and left open the question of proving similar bounds for adaptive decoders. We show m = Ω((n/log |Σ|)^q/(q?1)) without assuming that the decoder is nonadaptive. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Anticode-based locally repairable codes with high availability

This paper presents constructions of new families of locally repairable codes (LRCs) with small locality and high availability, where each code symbol can be recovered by using many (exponential in the dimension of the code) disjoint small sets (of size 2 or 3) of other code symbols. Following the method of Farrell, the generator matrices of our LRCs are obtained by deleting certain columns from the generator matrix of the Simplex code, where the deleted columns form different anticodes. Most of the resulting codes, defined over any finite field and in particular over the binary field, are optimal either with respect to the Griesmer bound, or with respect to the Cadambe–Mazumdar bound for LRCs, or both.     

High-rate LDPC codes from partially balanced incomplete block designs

Journal of Algebraic Combinatorics - This paper presents a combinatorial construction of low-density parity-check (LDPC) codes from partially balanced incomplete block designs. Since...     

On balanced bases

It is proved that either a given balanced basis of the algebra (n + 1)M₁ M_n or the corresponding complementary basis is of rank n + 1. This result enables us to claim that the algebra (n + 1)M₁ M_n is balanced if and only if the matrix algebra M_n admits a WP-decomposition, i.e., a family of n + 1 subalgebras conjugate to the diagonal algebra and such that any two algebras in this family intersect orthogonally (with respect to the form tr XY) and their intersection is the trivial subalgebra. Thus, the problem of whether or not the algebra (n + 1)M₁ M_n is balanced is equivalent to the well-known Winnie-the-Pooh problem on the existence of an orthogonal decomposition of a simple Lie algebra of type A_n–1 into the sum of Cartan subalgebras.     

On balanced bases

It is proved that either a given balanced basis of the algebra (n + 1)M₁ M_n or the corresponding complementary basis is of rank n + 1. This result enables us to claim that the algebra (n + 1)M₁ M_n is balanced if and only if the matrix algebra M_n admits a WP-decomposition, i.e., a family of n + 1 subalgebras conjugate to the diagonal algebra and such that any two algebras in this family intersect orthogonally (with respect to the form tr XY) and their intersection is the trivial subalgebra. Thus, the problem of whether or not the algebra (n + 1)M₁ M_n is balanced is equivalent to the well-known Winnie-the-Pooh problem on the existence of an orthogonal decomposition of a simple Lie algebra of type A_n–1 into the sum of Cartan subalgebras.Translated from Matematicheskie Zametki, vol. 77, no. 2, 2005, pp. 213–218.Original Russian Text Copyright © 2005 by D. N. Ivanov.This revised version was published online in April 2005 with a corrected issue number.     

Construction of nested balanced block designs, rectangular designs andq-ary codes

Construction of nested balanced incomplete block (BIB) designs, nested balanced ternary designs and rectangular designs from given nested BIB designs and resolvable BIB designs are described. New constructions ofq-ary codes from nested BIB designs and balanced bipartite weighing designs are also given.     

On homothetic balanced metrics

In this article, we study the set of balanced metrics given in Donaldson’s terminology (J. Diff. Geometry 59:479–522, 2001) on a compact complex manifold M which are homothetic to a given balanced one. This question is related to various properties of the Tian-Yau-Zelditch approximation theorem for Kähler metrics. We prove that this set is finite when M admits a non-positive Kähler–Einstein metric, in the case of non-homogenous toric Kähler-Einstein manifolds of dimension ≤ 4 and in the case of the constant scalar curvature metrics found in Arezzo and Pacard (Acta. Math. 196(2):179–228, 2006; Ann. Math. 170(2):685–738, 2009).