Alexei Ashikhmin, Bell Labs, Lucent Technologies

Title: Quantum Error Detection

This work is devoted to the problem of error detection with quantum codes. Unlike the classical case the definition of the undetected error event is not so transparent for quantum codes. In our work we define the notion of the quantum undetected error event under natural physical assumptions concerning transmission with error detection over the depolarizing channel.

This allows us to derive an expression for the probability of quantum undetected error as a function of the weight enumerator of a quantum code. In the second part of the work we show that there exist quantum codes whose probability of undetected error falls exponentially with the length of the code and derive bounds on this exponent. The lower (existence) bound for stabilizer codes is proved by a counting argument for classical self-orthogonal quaternary codes. Upper bounds for any quantum codes are proved by linear programming. We present two general solutions of the LP problem. Together they give an upper bound on the exponent of undetected error. The upper and lower asymptotic bounds coincide for a certain interval of code rates close to 1.

Christine Bachoc, University of Bordeaux, France

Title: Harmonic weight enumerators

Let F be a group alphabet of size q, and let C be a code over F, i.e. a subgroup of F^n. The Hamming weight enumerator of C is the polynomial W_C(x,y) homogeneous of degree n counting the number of codewords of given weight. The very famous MacWilliams identity relates the weight enumerator of C and the weight enumerator of its dual code. We generalize this identity to polynomials Z_{C,f}(x,y) associated to some f in L(F^n) the space of complex-valued functions on F^n. The function f must belong to an irreducible component of L(F^n) under the action of the group G:=S_{q-1}^n.S_n. In terms of association schemes, f belongs to the image of an idempotent of the non-binary Johnson scheme.

In the cases of binary, ternary and quantum self-dual codes, the polynomials Z_{C,f} are relative invariant polynomials for the group acting on the usual W_C. As an application, we obtain a strengthening of Delsarte's result on the existence of generalized designs on the codewords of fixed weight of extremal codes.

We also derive a method to compute the "intersection numbers" of such a code. Let u be a fixed word in F^n . The "intersection numbers" count the number of codewords of fixed weight, and belonging to a fixed orbit under the action of the stabilizer G_u of u in G. More explicitely: n_{w,[i,j]}(u)=Card { v : v in C | wt(v)=w , e(u,v)=w-i, n(u,v)=w-j} where e(u,v) is the number of equal and nonzero coordinates in u and v and n(u,v) is the cardinality of the intersection of their supports.

They can be used to compute the coset distribution of C, and to help the classification of extremal codes. Explicit computations in the quantum case will be presented.

Eiichi Bannai, Kyushu University

Title: Some results on modular forms motivated by coding theory

This talk is based on joint work with Masao Koike (Kyushu University), Akihiro Munemasa (Kyushu University) and Jiro Sekiguchi (Himeji Institute of Technology). First we give the determination of the finite index subgroups $\Gamma$ of the modular group $SL(2, Z)$ for which the space of modular forms (of integral weights) of $\Gamma$ is isomorphic to a polynomial ring. There are 17 such groups up to the conjugacy in $SL(2, Z).$ One example is $\Gamma = \Gamma (3)$, and this case is related to the space of weight enumerators of ternary self-dual codes and the polynomial invariants by the unitary reflection group (No. 4) of order 24.

Then we consider a similar problem for the space of modular forms of fractional weights. We show that if the space of modular forms of half-integral weights (with respect to some multiplier system) of $\Gamma$ is isomorphic to a polynomial ring generated by 2 modular forms of weight $1/2$, then $\Gamma$ must be one of the 191 subgroups up to the conjugacy in $SL(2, Z).$ One example is $\Gamma = \Gamma (4)$, and this case is related to the space of weight enumerators of binary Type II codes, and the polynomial invariants by the unitary reflection group (No. 8) of order 96.

Finally, we consider similar problems for the space of modular forms of $1/l$-integral weghts. We show that the space of modular forms of $1/5$-integral weights (with respect to a certain specified multiplier system) of $\Gamma (5)$ is isomorphic to a polynomial ring generated by 2 modular forms of weight $1/5$. Also, we discuiss the connections of this work with the classical work of F. Klein on the icosahedron and with the unitary reflection group (No. 16) of order 600.

The main theme here is that, in some cases, by considering the fractional weight modular forms, the ring of modular forms becomes simpler, and we can get better understanding of the space of modular forms of integral weights. We also mention some very recent work by T. Ibukiyama on modular forms of $1/7$-integral weight of $\Gamma (7)$, which was motivated by this theme.

Alexander Barg, Bell Labs, Lucent Technologies and IPPI, Moscow

Title: Polynomial method in coding theory

Polynomial, or Delsarte's, method in coding theory accounts for a variety of structural results on, and bounds on the size of, extremal configurations (codes and designs) in various metric spaces. We present a general framework for the method which includes some previous results as particular cases. We explain how this generalization leads to new asymptotic bounds on the performance of codes in various transmission channels and to a number of other results in combinatorial coding theory.

T. Beth, University of Karlsruhe, Germany

Title: Quantum computing - applicable algebra and discrete mathematics in physics

Jurgen Bierbrauer, Michigan Technological University

Postscript version

Title: Linear and additive codes: theory and applications

Our first application is from theoretical computer science: the reduction of the construction problem of $\epsilon -$biased arrays (probability spaces, random variables) and $\epsilon -$ dependent arrays to the efficient construction of good codes. Algebraic-geometric codes provide an asymptotically optimal solution for one variant of the problem.

However, as it may not be that easy to efficiently handle AG-codes like those high up in the tower of Artin-Schreier extensions as constructed by Garcia-Stichtenoth it will be a good idea to squeeze the utmost out of classical families related to the projective line and to Hermitian curves. We concentrate on genus 0, and hence on the derivates of Reed-Solomon codes.

Starting point is a simplified approach to the theory of cyclic codes. This leads to a generalization in a natural way: Twisted BCH-codes generalize cyclic codes from the linear to the additive (not necessarily linear) case. This family was introduced independently by McEliece, Hattori and G.Solomon ( Reed-Solomon subspace codes). We sketch a new approach to the theory of twisted codes.

One application consists in an explicit construction of families of quantum codes in arbitrary characteristic.

The new approach enables us to completely eliminate use of the general theory in some important parametric cases. We obtain an explicit description of a family of additive codes, which via concatenation and lengthening yield a 3-parameter family of linear 2-weight codes.

Another simplification is based on an explicit and rather elementary projection construction due to C.L.Chen. He applied the construction to classical caps (ovals, ovoids) in characteristic 2 . The resulting additive codes with minimum distance 4 have been used in computer memory systems.

Application of Chen projection to Reed-Solomon codes yields a large family of additive codes, which contains the codes proposed by the Caltech/JPL-people for use in deep-space communication. The original description relied on the theory of Reed-Solomon subspace codes.

Peter Boyvalenkov, Bulgarian Academy of Sciences

Postscript version

Title: Linear programming bounds for spherical codes and designs

The linear programming techniques for estimating the size of codes and designs on the $n$-dimensional Euclidean sphere ${\bf S}^{n-1}$ were introduced after 1975. The result was quite impressive: the new bounds appeared to be, in a sense, universal, and easy for calculation.

The background for the linear programming approach was developed by Delsarte, Goethals and Seidel [11} and Kabatiansky and Levenshtein [12]. They proved that real polynomials which possess certain properties (to be explained in the talk) can be used for obtaining upper bounds on the size of spherical codes (for fixed dimension and minimum distance) and lower bounds on spherical designs (for fixed dimension and strength). Moreover, suitable polynomials were proposed and universal bounds have been obtained.

In section 2 we discuss the logic of the linear programming bounds and the logic of the universal bounds, i.e. the Levenshtein bound for codes [13, 14] and the Delsarte-Goethals-Seidel bound for designs [11]. Althought extremal in some sense and the best possible in (infinitely) many cases, these bounds appear not to give the full strength of the linear programming [16, 4, 6, 10]. We show how the distance distributions of codes and designs attaining the universal bounds can be computed. This can be used for proving nonexistence results [2, 3, 5, 7, 8].

In section 3 we describe necessary and sufficient conditions for existence of better than the universal bounds. Such conditions are investigated and it can be shown that they are satisfied in (infinitely) many cases. However, the properties of these functions are not completely studied and we give some conjectures about their behaviour. When improvements are possible, we describe a method for calculating corresponding new bounds. A computer program for such computations will be presented.

Section 4 is devoted to a search of analytic form of the new bounds (in this way they would become universal in the same sense that the Levenshtein bound and the Delsarte-Goethals-Seidel bound are universal). This problem is solved for designs [15] and we explain our agruments toward analogous solutions for codes.

In section 5 we go beyond the pure linear programming. Indeed, the linear programming techniques can be combined with other (geometric, for example) ideas for investigations on the structure of putative good codes and designs. Again the problem for designs is easier and we describe improvements (either asymptotic and in concrete cases, such as the first open ones) of the Delsarte-Gothals-Seidel bound [9]. In other application, linear programming techniques are used to estimate other parameters of codes such as their distance distribution. This resulted [1] in obtaining new bound on the exponent of error probability of decoding for the best possible codes in the Gaussian channel.

  1. A.Ashikhmin, A.Barg, S.Litsyn, A new upper bound on the reliability function of the Gaussian channel, preprint.
  2. E.Bannai, R.M.Damerell, Tight spherical designs I, J. Math. Soc. Japan 31, 1979, 199-207.
  3. E.Bannai, R.M.Damerell, Tight spherical designs II, J. London Math. Soc. 21, 1980, 13-30.
  4. P.G.Boyvalenkov, Extremal polynomials for obtaining bounds for spherical codes and designs, Discr. Comp. Geom. 14, 167-183 (1995).
  5. P.G.Boyvalenkov, Computing distance distribution of spherical designs, Linear Algebra and Its Applications 226/228, 1995, 277-286.
  6. P.G.Boyvalenkov, D.P.Danev, S.P.Bumova, Upper bounds on the minimum distance of spherical codes, IEEE Trans. Inform. Theory 42, 1996, 1576-1581.
  7. P.G.Boyvalenkov, D.Danev, I.N.Landgev, On maximal spherical codes I, Proc. Eleventh Intern. Symp. AAECC, Paris 1995; Springer--Verlag Lecture Notes in Computer Science 948, 158-168.
  8. P.G.Boyvalenkov, D.Danev, I.N.Landgev, On maximal spherical codes II, J. Comb. Designs, to appear.
  9. P.G.Boyvalenkov, D.Danev, S.Nikova, Nonexistence of certain spherical designs of odd strengths and cardinalities, Discr. Comp. Geom. 21, 1999, 143-156.
  10. P.Boyvalenkov, S.Nikova, Improvements of the lower bounds on the size of some spherical designs, Math. Balkanica 12, 1998, 151-160.
  11. P.Delsarte, J.-M.Goethals, J.J.Seidel, Spherical codes and designs, Geom. Dedicata 6, 1977, 363-388.
  12. G.A.Kabatiansky, V.I.Levenshtein, Bounds for packings on a sphere and in space, Probl. Inform. Transm. 14, 1978, 1-17.
  13. V.I.Levenshtein, On choosing polynomials to obtain bounds in packing problems, Proc. Seventh All-Union Conf. on Coding Theory and Inform. Transm., Part II, Moscow, Vilnius, 1978, 103-108 (in Russian).
  14. V.I.Levenshtein, Universal bounds for codes and designs, Chapter 6 in Handbook of Coding Theory, Eds. V.Pless and W.C.Huffman, Elsevier Science B.V., 1998.
  15. V.Nikov, S.Nikova, Extremal polynomials of degree $\tau+2$ and $\tau+3$ which improve the Delsarte bound for $\tau$-designs, Proc. Intern. Workshop on Coding and Cryptography, Paris 1999, 361-365.
  16. A.M.Odlyzko, N.J.A.Sloane, New bounds on the number of unit spheres that can touch a unit sphere in $n$ dimensions, J. Comb. Theory A26, 1979, 210-214.

Joint work with Danyo Danev.

Paul Camion, University Paris-VI, France

Title: Codes over Z_{p^n} and Association Schemes

Postscript version

Claude Carlet, Universite de Caen

Postscript version

Title: Recent Results on Bent Functions

Let n be a positive even integer. A Boolean function defined on the set Vn of all binary words of length n is called bent if the Walsh (i.e. discrete Fourier, Hadamard) transform

$\displaystyle \widehat{f_\chi}(s)=\sum_{x \in V_n} (-1)^{f(x)+x \cdot s}$

of the real-valued function

$f_\chi (x)=(-1)^{f(x)}$

has constant absolute value. Because of Parseval's relation:

$\displaystyle \sum_{s \in V_n} \left( \widehat{f_\chi}(s) \right )^2 = 2^{2n}$,

f is bent if and only if for any

s, $\widehat{f_\chi}(s)$ is equal to $\pm 2^{n \over 2}$.

Equivalent definitions are the following:

The notion of bent function and the ability to produce large classes of bent functions are relevant to cryptography and to algebraic coding theory.

After having presented the recent constructions of bent functions and the characterizations of these functions in terms of finite geometries, we shall present some new directions in the attempt of classifying them and recent results on the generalizations of the notion to functions over residue class rings.

I. Chakravarti, U North Carolina, Chapel Hill

Title: Duality of hexads and hexagrams in a PG(2,4) and the configuration of 30 Baer subdesigns (7,4,2) in a (56,11,2) design

A hexad is a set of six points in a projective plane PG(2,4) no three of which are collinear and a hexagram is a set of six lines no three of which are concurrent.Given a hexad h ,there is a unique hexagram H which is disjoint from h.h and H can be regarded as duals of each other.The (56,11,2) design which is usually constructed from a two -class association scheme on 56 hexads which share 0 or 2 points with each other, can be equivalently constructed from 56 hexagrams (duals of the hexads ) which share 0 or 2 lines with each other.

The join of a pair of points of the hexad is called a Pascal line which can be used to identify three other hexads which share with h exactly the pair of points which define the Pascal line. There are 15 Pascal lines associated with h and 15 triplets of hexads, each member of the triplet sharing with h, a distinguished pair of points on h. Again, a pair of lines of H meet at a point called a Brianchon point which can be used to identify three other hexagrams which share with H exactly the two lines which define the Brianchon point. The three hexads which are duals of these three hexagrams share with h exactly a pair of points(the pairs are distinct ,though). Corresponding to the 15 Brianchon points,there are then 15 triplets of hexads sharing each with h exactly a pair of points.

In this paper, we show that the 30 triplets of hexads correspond to the 30 subdesigns (7,4,2) derived from the design(56,11,2) by fixing a block,say, the first and constructing "Hussein chains(or graphs) corresponding to each of the 45 elements of the first block. Thus each subdesign (7,4,2) corresponds to either a Pascal line or a Brianchon point.

Italo Dejter, Dimacs and University of Puerto Rico

Title: Ternary perfect domination of binary codes

Given a graph G, we say that a vertex subset S of G is a perfect dominating set (or PDS) of G if every vertex v of G not in S is neighbor of exactly one vertex of S.

P. Weichsel showed that each connected component of the subgraph induced by a PDS in the n-cube is a subcube and conjectured that S is uniform, i.e. all such components are isomorphic.

P. Ostergard and D. Weakley showed that the conjecture is false, by exposing a PDS S in the 13-cube whose induced subgraph has as connected components 26 4-cubes and 288 isolated vertices (which correspond to the nonzero words of the ternary Hamming code) and whose automorphism group is the general linear group GL(3,3).

We establish that the perfect dominating set of the 13-cube found by Ostergard and Weakley (as a counterexample to Weichsel's uniformity conjecture) exists very naturally in the ternary Hamming code of length 13, and has a very special geometric-combinatorial structure. This approach provides very short proofs of its characteristic properties

This is joint work with Kevin T. Phelps.

S.M. Dodunekov, Institute of Mathematics, Sofia, Bulgaria

Title: Bounds on the minimum block length of linear codes over finite fields

Eric Egge, University of Wisconsin - Madison

Postscript version

Title: A generalization of the Terwilliger algebra of a commutative association scheme

Given a commutative association scheme $\Gamma$, Terwilliger considered the $\C$-algebra generated by the associated Bose Mesner algebra $M$ and dual Bose Mesner algebra $M^*$. This algebra is now known as the Terwilliger algebra and is usually denoted by $T$. Terwilliger showed that each vanishing intersection number and Krein parameter of $\Gamma$ gives rise to a relation on certain generators of $T$. The existence of these relations makes $T$ useful in the study of commutative association schemes with many vanishing intersection numbers and Krein parameters. In particular, $T$ is useful in the study of $P$- and $Q$-polynomial association schemes, which play an important role in coding theory.

Terwilliger's relations determine much of the structure of $T$, though not all of it in general. To illuminate the role these relations play, we consider a certain generalization $\cT$ of $T$. To go from $T$ to $\cT$, we replace $M$ and $M^*$ with a pair of dual character algebras $C$ and $C^*$. We define $\cT$ by generators and relations; intuitively $\cT$ is the associative $\C$-algebra with identity generated by $C$ and $C^*$ subject to the analogues of Terwilliger's relations. $\cT$ is infinite dimensional and noncommutative in general. We construct an irreducible $\cT$-module which we call the primary module; the dimension of this module is the same as that of $C$ and $C^*$. We find two bases of the primary module; one diagonalizes $C$ and the other diagonalizes $C^*$. We compute the action of the generators of $\cT$ on these bases. We compute the central primitive idempotent of $\cT$ associated with the primary module in terms of the generators of $\cT$. We then use this central primitive idempotent to show that $\cT$ is a direct sum of two sided ideals $\cT_0$ and $\cT_1$ with $\cT_0$ isomorphic to a full matrix algebra.

Thomas Ericson, Linkoping University, Sweden

Title: Distance regular spherical codes

A spherical code is a finite point-set on the unit sphere in Euclidean n-space. The general problem is to find codes with large cardinality and large minimum distance. A spherical code is optimal if for given cardinality the minimum distance is largest possible.

Distance regular spherical codes are codes with a very high degree of regularity. They are closely related to association schemes. Any distance regular spherical code defines an association scheme. Conversely, to any association scheme there is a family of distance regular spherical codes. Several of the known optimal spherical codes are of this kind. As a special case we have the class of distance regular codes having only two distinct non-zero distances. These codes are generated by strongly regular graphs.

We will discuss the basic theory and we will mention a few of the best ones of the known distance regular spherical codes.

Joint work with Victor Zinoviev.

Tuvi Etzion, Technion, Haifa, Israel

Title: Tilings with Generalized Lee Spheres

We discuss the tilings of ${\cal R}^n$ with bodies which are of the well known Lee spheres. It is shown that if $n=2$ then there exists a tiling of ${\cal R}^n$ with any generalized Lee sphere of order $n$. Other tilings of ${\cal R}^n$ with generalized Lee spheres with radius one are also shown. All the tilings which we consider are nased on integer lattices.

Zoltan Furedi, University Illinois (Urbana-Champaign)

Title: Lotto, footballpool and other covering radius problems

The aim of this talk is to review connections between Tur\'an's (hyper)graph problem and other parts of Combinatorics, like Steiner systems, packings and coverings, constant weight codes, Kneser graphs.

The code $C$ is called a covering code of $X$ with radius $r$ if every element of $X$ is within Hamming distance $r$ from at least one codeword from $C$. Given $X$ we are interested in a minimum sized $C$. Continuing a work of Hanani, Ornstein and S\'os, and Brouwer we determine the Lottery number, $L(n,k,p,2)$, the minimum number of $k$-subsets of an $n$-set such that all the ${n \choose p}$ $p$-sets are intersected by one of them in at least $2$ elements, for all $n> n_0(k,p)$. Answering a question of H\"am\"al\"ainen, Honkala, Litsyn and \"Ostergard we show further connections between Tur\'an theorem and constant weight covering codes.

Markus Grassl, Universitaet Karlsruhe, Germany

Title: An ensemble of properties of classical codes useful for quantum codes

Quantum error-correcting codes (QECC) can be constructed using classical error-correcting codes. The first construction, developed independently by Calderbank & Shor and by Steane, is based on weakly self-dual binary codes. The second, more general one, was derived by Calderbank, Rains, Shor, and Sloane, and in an equivalent formulation, by Gottesman. It is based on codes over GF(4).

The investigation of the properties of the resulting QECC lead to unusual questions and results about classical codes. In the talk, I will present these results together with the corresponding motivation from quantum error correction and quantum computation.

First, I will establish a connection between the distance of a coset to the code and a sum over powers of the Hamming weights of the dual codewords. Second, I will answer the question when a weakly self-dual cyclic binary code is doubly even. Finally, a construction of classical codes suitable for QECC is given. This construction is based on codes over extension fields.

Laurent Habsieger, University of Bordeaux, France

Title: On integeral zeros of Krawtchouk polynomials

Krawtchouk polynomials may be defined by $$K_n(x,q,N)=\sum_{j=0}^n (-1)^j(q-1)^{n-j}{N-x\choose n-j}{x\choose j}\,.$$ Properties of their zeros occur in many combinatorial problems, such as graph theory and coding theory. For instance, when $K_n(x,q,N)$ has a noninteger root, there is no perfect code of radius $n$ on $\Bbb F_q^N$. Although this coding problem has been solved using extra tools, it still an open problem to determine which Krawtchouk polynomials have a noninteger root.

We shall give a survey on what is known about the integral zeros of Krawtchouk polynomials. We shall also present new results about their number and about the existence of a noninteger root.

Iiro Honkala, University of Turku, Finland

Title: On identifying codes

A binary code $C$ of length $n$ is called $t$-identifying if for all $x$ in $F^n$ the intersections $B_t(x) \cap C$ are nonempty and different, where $B_t(x)$ denotes the Hamming ball of radius $t$ centred at $x$. We consider bounds on the minimum cardinality of such codes.

More generally, we can consider the same problem in an arbitrary graph $G = (V,E)$. Denote $B_t(v) = \{ x\in V: d(x,v) \leq t\}$, where now $d(x,v)$ denotes the number of edges in any shortest path between $x$ and $v$. A subset $C$ of the vertex set $V$ is called an identifying code if the sets $B_t(x) \cap C$ are nonempty and different for all vertices $x \in V$. Interesting cases that have been considered include infinite rectangular and hexagonal grids.

The problem was introduced in M.G. Karpovsky, K. Chakrabarty and L.B. Levitin: "On a new class of codes identifying vertices in graphs", {\it IEEE Trans. Inform. Theory}, vol. 44, pp. 599-611, 1998.

D. Jaffe, University of Nebraska, Lincoln

Title: Linear programming bounds for long codes

Data will be presented showing (for hundreds of d values) the largest k for which the existence of a [1000,k,d] binary linear code does not violate the Delsarte-MacWilliams inequalities. This data was gathered using the author's program Split, which will be interactively demonstrated in the talk.

Gregory Kabatiansky, IPPI, Moscow

Title: The Mastermind game, the rigidity of Hamming spaces and superimposed codes

A new approach to investigating the Mastermind game and related search problems based on ideas and methods of coding theory is proposed. This approach makes possible improved bounds on various problems associated with the rigidity of Hamming spaces.

We call a set B a base of a metric space L if every point of L is uniquely determined by its distances to the points of B. The minimal possible number of points of a base we call the rigidity of the metric space. This notion was introduced in 1963 by P. Erdosh and A. Renyi for solving the following weighing problem: what is the minimal number W(n) of weightings on an accurate scale to determine all false coins in a set of n coins. It is easy to see that the minimal number of queries with deterministic strategy differs by not more than on one from the rigidity r(2,n) of the binary n-dimensional Hamming space.

It is known that r(2,n) is asymptotically equal to 2n/logn, where log is binary (B. Lindstrom 1964-66). For nonbinary case only upper and lower bounds on r(q,n) are known(V.Chvatal,1983). In this talk we prove that for the ternary case the answer has the same form as for the binary with replacing binary log on ternary,and we make some improvements for the both types of bounds for $q>3$. We show also the relationship among these problems, superimposed codes and codes for summation channels.

Levon Khachatrian, University of Bielefeld, Germany

Title: Maximal number of constant weight vertices of the unit n-cube contained in a k-dimensional subspace

We determine the maximal possible number of vertices of weight w in the unit n-cube contained in a k- dimensional subspace of the n-dimensional Euclidean space.

E. Knill, Los Alamos National Lab

Title: Classical and quantum error-correcting codes as subsystems

Error correction is necessary to protect information against noise. Consider the following situation: We wish to record the value of one bit for future retrieval. Available are three bits, of which we know that only the last two are affected by noise. How should we record the value to ensure that it persists? Clearly, the value is stored in the first bit. Although we can associate a traditional code with this method of error protection, it is more natural to describe this situation as above: The protected information is in a subsystem (the first bit), which is unaffected by noise. A surprising lesson learned from quantum error correction is that every error-correcting code arises in this fashion for an abstract subsystem. I will lay out the foundations for a general theory of classical and quantum error-correction which extends the notions of minimum distance, $e$-error-correction, and works for any reasonable model of noise.

Tero Laihonen, University of Turku, Finland

Title: On an Algebraic Method for Bounding the Covering Radius

A combinatorial parameter of a code called covering radius gives information on geometric properties of the code. An algebraic method for estimating this parameter is discussed. We will survey the known bounds on covering radius with a given dual distance and derive a new one. The new bound improves on the known results for covering radius in a certain range of dual distances. The used method is also somewhat simpler than the approach leading to the best previously known estimate in that range.

V.I. Levenshtein, Keldysh Inst. Appl. Math, Moscow

Title: Introduction: Codes and association schemes


Title: A general notion of a t-design and a universal bound on its size

Simon Litsyn, Tel Aviv University, Israel

Title: Applications of the polynomial method to some combinatorial coding problems

We discuss several applications of the polynomial method to some problems of coding theory. First we formulate an approach allowing estimation of the distance distributions by an appropriate choice of polynomials. This leads to upper and lower bounds on components of the distance distributions of some codes. Then we consider combinatorial problems where a knowledge of distance distribution is of essential importance. This allows us to derive new bounds in such problems as:

1) Upper bounds on generalized weights improving on the bounds by Vladuts and Cohen-Litsyn-Zemor;

2) Upper bounds on the radius of the decoding sphere for the the list-2 codes improving on the bound by Blinovskii;

3) Upper bounds on the minimum distance of doubly-even self-dual codes improving on the bound by Ward and Conway-Sloane;

4) Upper bound on the size of Sidon sets of binary vectors improving on the bound by Lindstrom.

William Martin, University of Winnipeg/University of Waterloo

Title: From synchronization to integration: linear programming bounds for RT codes and $(T,M,S)$-nets

A $(T,M,S)$-net in base $b$ is an evenly distributed set of $b^M$ points in the Euclidean unit cube $[0,1)^S$. (The ``quality parameter'' $T$ is preferably close to zero.) These deterministic distributions are of great importance in quasi-Monte Carlo integration and other applications to numerical analysis.

In 1996, an important theorem was proved by Mullen and Schmid and, independently, by Lawrence which shows that $(T,M,S)$-nets are equivalent to a special class of {\em ordered orthgonal arrays}. This has led to a flurry of activity as combinatorial techniques and constructions are extended to this new setting. In some of my recent joint work with Doug Stinson and Terry Visentin, ideas from coding theory, combinatorial designs, and association schemes are successfully brought to bear on this problem.

As it turns out, there is a dual concept to that of an ordered orthogonal array, which I will call an {\em RT code}. These arise in several contexts; for instance, as error-correcting codes for a ``synchronization error'' channel. For small group size, these codes have some connection to other topics of interest.

In this talk, I will show that all of the basic elements of Delsarte theory can be extended to this rich setting. These include MacWilliams identities, linear programming bounds, a sphere-packing bound, a Rao bound, both Plotkin and dual Plotkin bounds and more. Transferring this information back to the Euclidean world, we obtain the best known lower bounds on the quality parameter $T$ for $(T,M,S)$-nets.

Mikhail Muzychuk, Bar-Ilan U., Israel

Postscript version

Title: Introduction to circulant association schemes and their applications

A circulant graph on $n$ points is a Cayley graph over a cyclic group ${\Bbb Z}_n$. It is completely defined by its connection set $S\subseteq \Z_n$. It is a trivial observation that two circulants with connection sets $S$ and $mS,m\in\Z_n^*$ are isomorphic. The converse is not true in general. The following problem is known as the isomorphism problem for circulants.

Given two circulant graphs ${\sf Cay}(\Z_n,S)$ and ${\sf Cay}(\Z_n,T)$. Find an effective algorithm which recognizes an isomorphism between them.

This problem may be naturally extended to Cayley graphs. In our talk we shall discuss connections between the isomorphism problem for Cayley graphs, Cayley association shemes and Schur rings. We also give an overview of the recent results related to the isomorphism problem for circulants.

Joint work with M. Klin and R. Poschel.

Dmitrii Nogin, IPPI, Moscow

Title: Generalized Hamming Weight as a Weight Function

We prove that the weight function of a linear code, that is, an integer function defined on the vector space of messages, uniquely determines the code up to equivalence. We propose a natural way to extend the r-th generalized Hamming weight, that is, a function on r-subspaces of a code, to a function on the r-th exterior power of the code. Using this, we show that for any linear code C and any integer r not greater than the dimension of C, another code C' exists whose weight distribution corresponds to a part of the generalized weight spectrum of C from the r-th weights to the k-th. In particular, the minimum distance of C' is proportional to the r-th generalized weight of C.

Vera Pless,University of Illinois, Chicago

Title: On the Classification of Extremal Additive Codes over GF(4)

We discuss the status of the classification of the extremal additive codes over GF(4) which are self-dual under the trace inner product. These codes are of interest because of their connection to quantum codes. There are 5 inequivalent extremal codes of length 8, 8 of length 9, at least 56 of length 10, and exactly 1 of length 11. We discuss the methods of classification, the concepts of lengthening and shortening, and connections to binary codes.

Joint work with P. Gaborit, W.C. Huffman, and J.-L. Kim.

D. Ray-Chaudhuri, Ohio State U.

Title: New Ternary Quasi Cyclic Codes With Better Minimum Distances

The generating matrices and the weight enumerators of 20 new record-breaking ternary quasi-cyclic codes have been found using algebraic techniques and some computer search.

Joint work with Irfan Siap and Nuh Aydin.

Miklos Ruszinko, Hungarian Academly of Sciences, Budapest

Title: On superimposed codes

What is the maximum number of subsets of an n-element set satisfying the condition that no set is covered by the union of r others? For r=1 the well-known Sperner Theorem answers this question. For all other values of r the question is still open although it has been intensively investigated in the last forty years in different branches of mathematics, i.e., combinatorics, coding theory, computer science, etc. We will present results and some models where this question has been investigated. We will present some new results on the geometric version of this problem, too. The letter ones were obtained with Zoltan Furedi.

Alex S. Samorodnitsky, IAS

Title: On the optimum of Delsarte's linear program

We show that Delsarte's linear programming upper bounds on the rate of binary codes and constant weight binary codes strictly exceed the Gilbert-Varshamov lower bounds. In fact we show, that Delsarte's upper bound is at least as big, as the average of the Gilbert-Varshamov bound and the McEliece, Rodemich, Rumsey and Welch upper bound.

Stefan E. Schmidt, M.I.T.

Title: Moebius Inversion in Coding Theory

Moebius inversion on partially ordered sets was significantly promoted by G.-C. Rota in the 1960s and since then has been proven to be a powerful tool in modern Combinatorics.

In connection with certain weight functions on finite rings, Moebius inversion turned out to be rather fruitful, also in Coding Theory. This will be outlined in my talk on a recent joint research project with Marcus Greferath at the AT&T Labs. One of the applications given will be a combinatorially proof of MacWilliams equivalence theorem for a large class of rings.

N. Sendrier, INRIA

Title: Structural attacks on code-based cryptosystems and related problems

There are two kinds of attacks on public key cryptosystems based on codes: decoding attacks (investigated at length these past years) and structural attacks. The structural cryptanalysis reveals many interesting problems of coding theory. The most general one is the following: "Given (the generating matrix of) a code, find a decoder for it". This general problem is (too) difficult, but if we add that the code should be equivalent to some very structured other one (Reed-Solomon, concatenated, Goppa, ...), the problem sometimes become easier.

We will review which structures are easy to "recognize" and which are not, and we will also discuss the relationships with problems like code equivalence or automorphism group computation.

Neil J. A. Sloane, AT&T Shannon Lab

Title: Packings in Grassmannian Spaces

How should you place 18 planes through the origin in Euclidean 4-space so that they are as far apart as possible? More generally, how do you place N points on the Grassmannian manifold G(m,n) so they are as far apart as possible? I will discuss bounds and constructions, including several infinite families of optimal packings. There are surprising connections with quantum codes, group theory and spherical t-designs (and of course statistics, for the graphical representation of multi-dimensional data).

This is based on joint work with Calderbank, Conway, Hardin, Rains, Shor.

For more information see :

Ulrich Tamm, U.-Bielefeld, Germany

Postscript version

Title: Communication Complexity and Orthogonal Polynomials

The communication complexity C(f) is the number of bits that two persons have to exchange in order to evaluate the function f(x,y) when initially one person only knows the argument x and the other person only knows y. Communication complexity, as introduced by Yao in 1979, turned out to be an important topic in Computer Science, especially in the derivation of bounds for area-time tradeoff in VLSI-layout and for depth of circuits, decision trees and branching programs.

We shall study the communication complexity of functions like the Hamming distance whose function matrices arise from association schemes. Since the rank of these matrices yields a lower bound on C(f), close bounds on C(f) are obtained if the eigenvalues, which are orthogonal polynomials, are different from 0. For the Hamming distance, C(f) can almost exactly be determined if there are only very few integral zeros of Krawtchouk polynomials. Also related functions, like the parity of the Hamming distance will be studied.

Paul Terwilliger, University of Wisconsin-Madison

Title: Association schemes and the Q polynomial property

The association schemes that are most important in coding theory, such as the hypercubes and the Johnson schemes, have what is known as the Q polynomial property. I have always thought this was a deep and rather mysterious property, and for years I have been searching for ways to understand it better. This search lead me to the notion of a Leonard pair. This is a purely algebraic notion that seems to capture the essence of the Q polynomial property. I call it a Leonard pair because it is closely related to a theorem of Doug Leonard concerning the Askey-Wilson polynomials. I define a Leonard pair to be an ordered pair A,B of linear transformations on a finite dimensional vector space V that satisfy both conditions below:

(i) There exists a basis for V with respect to which the matrix representing A is diagonal, and the matrix representing B is irreducible tri-diagonal.

(ii) There exists a basis for V with respect to which the matrix representing B is diagonal, and the matrix representing A is irreducible tri-diagonal.
We recall a tridiagonal matrix is irreducible whenever all entries immediately above and below the main diagonal are nonzero.

In my talk, I will outline a simple classification of the Leonard pairs, and discuss the connection to the Q polynomial property.

J.H. van Lint, Eindhoven, the Netherlands

Title: On perfect ternary constant weight codes

We consider the space of ternary words of length n and fixed weight w with the usual Hamming distance. We are interested in perfect single-error-correcting codes in such spaces. A construction of an infinite sequence of such codes is presented, where n is a power of 2 and w = n-1. We prove that there are no other parameters for which such codes exist except if w = n (in which case the codes are actually binary Hamming codes).

Paul-Hermann Zieschang, University of Kiel, Germany

Title: Groups + Buildings = Association Schemes

An association scheme is a set X together with a family R of binary relations on X satisfying a few regularity conditions. Examples are provided by groups G acting transitively on X: Take R as the totality of G-orbits in the Cartesian product X x X (under componentwise action).

With the help of the (well-known) concatenation of binary relations we define a multiplication on the power set of R. This multiplication enables us to view association schemes as algebraic objects. In particular, it puts us in a position to develop an algebraic structure theory (for association schemes) which in large parts can be modelled on the theory of groups. We break up this structure theory into three parts, the local theory, the representation theory, and the theory of generators.

We shall push the local theory up to the ``Jordan-H\"older Theorem'' for association schemes. This exhibits the role of the simple schemes in the general theory.

As a typical representation theoretical result we shall present the generalization of Maschke's Theorem on the semisimplicity of the group algebra to the theory of association schemes.

We shall mainly be interested in the third part of the theory, the theory of generators. This part provides us naturally with geometries. In particular, buildings come into the game. It turns out that, within the theory of association schemes, the buildings play exactly the same role which, in group theory, is played by the Coxeter groups. This opens the door to a new, to a completely algebraic treatment of the class of buildings. We shall present results on buildings which are obtained by elementary scheme-theoretical technics.