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     

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     

An improvement of discrete Tardos fingerprinting codes

It has been proven that the code lengths of Tardos’s collusion-secure fingerprinting codes are of theoretically minimal order with respect to the number of adversarial users (pirates). However, the code lengths can be further reduced as some preceding studies have revealed. In this article we improve a recent discrete variant of Tardos’s codes, and give a security proof of our codes under an assumption weaker than the original Marking Assumption. Our analysis shows that our codes have significantly shorter lengths than Tardos’s codes. For example, when c = 8, our code length is about 4.94% of Tardos’s code in a practical setting and about 4.62% in a certain limit case. Our code lengths for large c are asymptotically about 5.35% of Tardos’s codes. A part of this work was presented at 17th Applied Algebra, Algebraic Algorithms, and Error Correcting Codes (AAECC-17), Bangalore, India, December 16–20, 2007.     

An extremum problem for polynomials related to codes and designs

We give a solution to Yudin’s extremum problem for algebraic polynomials related to codes and designs. Translated fromMatematicheskie Zametki, Vol. 67, No. 4, pp. 508–513, April, 2000.     

A combinatorial characterization of smooth LTCs and applications

The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet, we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate‐limit of LTCs and whether asymptotically good linear LTCs with constant query complexity exist. In this paper, we provide a combinatorial characterization of smooth locally testable codes, which are locally testable codes whose associated tester queries every bit of the tested word with equal probability. Our main contribution is a combinatorial property defined on the Tanner graph associated with the code tester (“well‐structured tester”). We show that a family of codes is smoothly locally testable if and only if it has a well‐structured tester. As a case study we show that the standard tester for the Hadamard code is “well‐structured,” giving an alternative proof of the local testability of the Hadamard code, originally proved by (Blum, Luby, Rubinfeld, J. Comput. Syst. Sci. 47 (1993) 549–595) (STOC 1990). Additional connections to the works of (Ben‐Sasson, Harsha, Raskhodnikova, SIAM J. Comput 35 (2005) 1–21) (SICOMP 2005) and of (Lachish, Newman and Shapira, Comput Complex 17 (2008) 70–93) are also discussed. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 280–307, 2016     

线性码译码的一种算法

线性码译码的一种算法杜宏（中国科学院系统科学研究所，北京１０００８０）１９９２年３月２５日收到．引言线性码的译码算法一直是一个公开问题．Ｊ．Ｊｕｓｔｅｓｅｎ等人在文［２］中给出了平面代数曲线上代数几何码译码的一种算法之后，Ａ．Ｎ．Ｓｋｏｒｏｂｏｇａｔ...     

Champs affines

The purpose of this work is to introduce a notion of affine stacks, which is a homotopy version of the notion of affine schemes, and to give several applications in the context of algebraic topology and algebraic geometry. As a first application we show how affine stacks can be used in order to give a new point of view (and new proofs) on rational and p-adic homotopy theory. This gives a first solution to A. Grothendieck’s schematization problem described in [18]. We also use affine stacks in order to introduce a notion of schematic homotopy types. We show that schematic homotopy types give a second solution to the schematization problem, which also allows us to go beyond rational and p-adic homotopy theory for spaces with arbitrary fundamental groups. The notion of schematic homotopy types is also used in order to construct various homotopy types of algebraic varieties corresponding to various co-homology theories (Betti, de Rham, l-adic, ...), extending the well known constructions of the various fundamental groups. Finally, just as algebraic stacks are obtained by gluing affine schemes we define $$ \infty $$-geometric stacks as a certain gluing of affine stacks. Examples of $$ \infty $$-geometric stacks in the context of algebraic topology (moduli spaces of dga structures up to quasi-isomorphisms) and Hodge theory (non-abelian periods) are given.     

Champs affines

The purpose of this work is to introduce a notion of affine stacks, which is a homotopy version of the notion of affine schemes, and to give several applications in the context of algebraic topology and algebraic geometry. As a first application we show how affine stacks can be used in order to give a new point of view (and new proofs) on rational and p-adic homotopy theory. This gives a first solution to A. Grothendieck’s schematization problem described in [18]. We also use affine stacks in order to introduce a notion of schematic homotopy types. We show that schematic homotopy types give a second solution to the schematization problem, which also allows us to go beyond rational and p-adic homotopy theory for spaces with arbitrary fundamental groups. The notion of schematic homotopy types is also used in order to construct various homotopy types of algebraic varieties corresponding to various co-homology theories (Betti, de Rham, l-adic, ...), extending the well known constructions of the various fundamental groups. Finally, just as algebraic stacks are obtained by gluing affine schemes we define $$ \infty $$-geometric stacks as a certain gluing of affine stacks. Examples of $$ \infty $$-geometric stacks in the context of algebraic topology (moduli spaces of dga structures up to quasi-isomorphisms) and Hodge theory (non-abelian periods) are given.     

Gray Codes,Loopless Algorithm and Partitions

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process.      

Completely simple codes

A code X is said to be completely simple if the kernel of the syntactic monoid of X ^? is a completely simple semigroup. This class of codes is a common generalization of two important classes of codes, that is, thin codes and group codes, and has remarkable algebraic and combinatorial properties. In this paper, we give systematic characterizations of completely simple codes and, in particular, show that many fundamental properties of thin codes are preserved in this generalization.     

Locally trivial 𝔾a−actions on ℂ5 with singular algebraic quotients

Simple examples are given of proper algebraic actions of the additive group of complex numbers on ?⁵ whose geometric quotients are, respectively, a?ne, strictly quasia?ne, and algebraic spaces which are not schemes. Moreover, a Zariski locally trivial action is given whose ring of invariant regular functions defines a singular factorial a?ne fourfold embedded in ?¹². The geometric quotient for the action embeds as a strictly quasia?ne variety in the smooth locus of the algebraic quotient with complement isomorphic to the normal a?ne surface with the A₂?singularity at the origin.     

Translation planes and derivation sets

Using ideas from algebraic coding theory, a general notion of aderivation set for a projective plane is introduced. Certain geometric codes are used to locate such sets. These codes also lead to upper bounds for thep-ranks of incidence matrices of translation planes in terms of the dimensions of the associated codes.Dedicated to Professor Tallini on the occasion of his 60 ^th birthdayThis research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.     

On Linear Programming Bounds for Spherical Codes and Designs

We investigate universal bounds on spherical codes and spherical designs that could be obtained using Delsartes linear programming methods. We give a lower estimate for the LP upper bound on codes, and an upper estimate for the LP lower bound on designs. Specifically, when the distance of the code is fixed and the dimension goes to infinity, the LP upper bound on codes is at least as large as the average of the best known upper and lower bounds. When the dimension n of the design is fixed, and the strength k goes to infinity, the LP bound on designs turns out, in conjunction with known lower bounds, to be proportional to k^n-1.     

Some new results on superimposed codes

A (w,r) cover‐free family is a family of subsets of a finite set such that no intersection of w members of the family is covered by a union of r others. A (w,r) superimposed code is the incidence matrix of such a family. Such a family also arises in cryptography as the concept of key distribution pattern. In the present paper, we give some new results on superimposed codes. First we construct superimposed codes from super‐simple designs which give us results better than superimposed codes constructed by other known methods. Next we prove the uniqueness of the (1,2) superimposed code of size 9 × 12, the (2,2) superimposed code of size 14 × 8, and the (2,3) superimposed code of size 30 × 10. Finally, we improve numerical values of upper bounds for the asymptotic rate of some (w,r) superimposed codes. © 2004 Wiley Periodicals, Inc.     

Théorème de l’Indice et Formule des Traces

Our purpose is to obtain a geometric formula as explicit as possible for the L ² index of a Dirac operator over a locally symmetric space of finite volume, generalizing Arthur’s formula for the Euler–Poincaré caracteristic (Arthur in Invent Math 97:257–290, 1989).     

An algebraic approach to Cichelli's perfect hashing

The aim of this paper is to describe a new approach to building minimal and perfect hash functions for a predefined set of keys. Several papers have dealt with this problem and proposed various kinds of functions. This study is based on a function whose address depends both on the letter codes and the letter position in the key, and therefore represents an extension of Cichelli's function. The weights associated with the position are considered to be fixed, and letter code computing is considered to be an interpolation problem. As a result, hash building only requires the solution of an algebraic linear system and then the time complexity is polynomialO(n ³).     

The information cocycle andɛ-bounded codes

We shall prove here that Bowen’s bounded codes lead to a cocycle-coboundary equation which can be exploited in various ways: through central limit theorems, through the related information variance or through a certain group invariant. Another result which emerges is that it is impossible to boundedly code two Markov automorphisms when one is of maximal type and the other is not. The functions which appear in the above cited cocycle-coboundary equation may belong to variousL ^p spaces. We devote a section to this problem. Finally we show that the information cocycle associated with small smooth partitions of aC ² Anosov diffeomorphism preserving a smooth probability is, in a sense, canonical.