Coding theory and bilinear complexity

The subject of the present book is naturally divided into three parts. The first part (Chapter 1) deals with the $\textit{theory of linear error correcting codes}$. Here one is interested in the mathematical theory of secure information transmission, e.g., satellite communication. This should not be confused with cryptology where the aim is to guard information against unauthorized access. The second part of the book (Chapters 3, 5, 6, and 7) deals with the theory of $\textit{algebraic function fields}$ and applies this theory to the so-called $\textit{modular function fields}$. These function fields- or equivalently, algebraic curves-arise from compactifications of the fundamental domain of the action of certain subgroups of SL$_{2}$(Z) on the upper half plane. Reductions of these curves modulo primes p (outside a finite set of special primes) yields series of algebraic curves over finite fields with many rational points. Finally, the last part of this book (Chapters 8-10) is devoted to a treatment of bilinear complexity theory. Here one is interested in the minimal number of multiplications necessary to compute bilinear forms. One of the most famous representatives of this class of problems is that of determining the asymptotic complexity of matrix multiplication. The first two subjects merge to the theory of "Geometric Goppa-Codes" , also known as "Algebraic-Geometric Codes" which is discussed in Chapter 3. There exists excellent literature on this subject, among which we only mention [42]. For obtaining asymptotically good linear codes from geometric Goppa codes, the main problem is the construction of sequences of curves with many rational points, as is described in Chapter 4. On the contrary to the theory of error-correcting codes or that of algebraic curves over finite fields, there does not yet exist an up to date concise treatment of the theory of bilinear complexity$^{1}$. Therefore we have decided to give a brief account of the theory which meets our demands in Chapter 8. With the tools developed there we shall see in Chapter 9 that coding theory can be applied to obtain lower bounds in complexity theory in the following sense: one can translate the complexity of a given bilinear map into the problem of determining a linear code of minimal block length when the dimension and the minimum distance are [...