A combination of testability and decodability by tensor products

Ben‐Sasson and Sudan (RSA 2006) showed that taking the repeated tensor product of linear codes with very large distance results in codes that are locally testable. Due to the large distance requirement the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result to present a combinatorial construction of locally testable codes with largest known rate. As a consequence, this construction was obtained over sufficiently large fields. In this paper we improve the result of Ben‐Sasson and Sudan and show that for any linear codes the associated tensor products are locally testable. Consequently, the construction of Meir can be taken over any field, including the binary field. Moreover, a combination of our result with the result of Spielman (IEEE IT, 1996) implies a construction of linear codes (over any field) that combine the following properties:

• have constant rate and constant relative distance;
• have blocklength n and are testable with n^? queries, for any constant ? > 0;
• linear time encodable and linear‐time decodable from a constant fraction of errors.

Furthermore, a combination of our result with the result of Guruswami et al. (STOC 2009) implies a similar corollary for list‐decodable codes. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 572–598, 2015     

A combinatorial characterization of quadrics

In this paper we prove that in a projective space of dimension three and orderq the two plane characterk-sets fork {q ²+ 1,(q+1)²} are of the same type as the elliptic or the hyperbolic quadric, respectively. As a corollary we obtain a characterization of the elliptic and the hyperbolic quadrics.     

A characterization of alternating groups

It is proved that a group G generated by a conjugacy class X of elements of order 3, so that every two non-commuting elements of X generate a subgroup isomorphic to an alternating group of degree 4 or 5, is locally finite. More precisely, either G contains a normal elementary 2-subgroup of index 3, or G is isomorphic to an alternating group of permutations on some (possibly infinite) set.Supported by RFBR grant Nos. 02-01-00495 and 02-01-39005, by FP Universities of Russia grant No. UR.04.01.0202, and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1.Translated from Algebra i Logika, Vol. 44, No. 1, pp. 54–69, January–February, 2005.     

A combinatorial characterization of Boolean algebras

In this paper we prove that a groupoid is term equivalent to a Boolean algebra if and only if the number of n-ary term operations of the groupoid is equal to 2²ⁿ2^{2^n} for n = 0, 1, 2 and 3. This yields a partial solution of a problem posed by Berman in 1986.     

A similarity principle for complex vector fields and applications

This paper establishes a similarity principle for a class of non-elliptic, smooth complex vector fields in the plane. This principle is used to prove a uniqueness result for a nonlinear Cauchy problem.

     

A formula on the weight distribution of linear codes with applications to AMDS codes

The determination of the weight distribution of linear codes has been a fascinating problem since the very beginning of coding theory. There has been a lot of research on weight enumerators of special cases, such as self-dual codes and codes with small Singleton's defect. We propose a new set of linear relations that must be satisfied by the coefficients of the weight distribution. From these relations we are able to derive known identities (in an easier way) for interesting cases, such as extremal codes, Hermitian codes, MDS and NMDS codes. Moreover, we are able to present for the first time the weight distribution of AMDS codes. We also discuss the link between our results and the Pless equations.     

A combinatorial characterization of the Klein quadric

We give a combinatorial characterization of the Klein quadric in terms of its incidence structure of points and lines. As an application, we obtain a combinatorial proof of a result of Havlicek.In memoriam Giuseppe TalliniWork supported by National Research Project Strutture Geometriche, Combinatoria e loro applicazioni of the Italian Ministere dell'Università e della Ricerca Scientifica and by G.N.S.A.G.A. of C.N.R.      

线性缓冲算子矩阵及其应用研究

在缓冲算子公理体系下,构造了一类线性的弱化缓冲算子和强化缓冲算子,并定义了这类缓冲算子的算子矩阵,研究了它们的一些特性,并以此证明了m阶算子作用的计算公式,最后实例验证了算子的有效性与实用性.     

A combinatorial characterization of normalizations of Boolean algebras

In this paper we prove that if a groupoid has exactly distinct n-ary term operations for n=1, 2, 3 and the same number of constant unary term operations for n=0, then it is a normalization of a nontrivial Boolean algebra. This, together with some general facts concerning normalizations of algebras, which we recall, yields a clone characterization of normalizations of nontrivial Boolean algebras: A groupoid (G;·) is clone equivalent to a normalization of a nontrivial Boolean algebra if and only if the value of the free spectrum for (G;·) is for n = 0, 1, 2, 3. In the last section the Minimal Extension Property for the sequence (2, 3) in the class of all groupoids is derived. Received September 15, 2004; accepted in final form October 4, 2005.     

A combinatorial result with applications to self-interacting random walks

We give a series of combinatorial results that can be obtained from any two collections (both indexed by Z×N) of left and right pointing arrows that satisfy some natural relationship. When applied to certain self-interacting random walk couplings, these allow us to reprove some known transience and recurrence results for some simple models. We also obtain new results for one-dimensional multi-excited random walks and for random walks in random environments in all dimensions.     

A combinatorial characterization of certain universal classes of hash functions

A new lower bound on the size of ?-almost strongly universal₂ classes of hash functions has recently been obtained by Stinson [8]. In this article we present a characterization of ? ? ASU₂ classes of hash functions meeting the Stinson bound in terms of combinatorial designs. © 1994 John Wiley & Sons, Inc.     

A new characterization of supercompactness and applications

We give a new characterization of λ-supercompact cardinal κ in terms of (κ,λ)-Solovay pairs. We give some applications of (κ,λ)-Solovay pairs.     

A characterization of smooth normed linear spaces

In this paper a new characterization of smooth normed linear spaces is discussed using the notion of proximal points of a pair of convex sets. It is proved that a normed linear space is smooth if and only if for each pair of convex sets, points which are mutually nearest to each other from the respective sets are proximal.