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
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
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.
Joint work with Danyo Danev.
Paul Camion, University Paris-VI, France
Title: Codes over Z_{p^n} and Association Schemes
Claude Carlet, Universite de Caen
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:
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
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
and
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
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.
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.
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.
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.
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
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:
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.
www.research.att.com/~njas/doc/yama.ps
or
www.research.att.com/~njas/doc/yama.pdf
We recall a tridiagonal matrix is irreducible whenever all entries
immediately above and below the main diagonal are nonzero.