Applied Algebra Group at the University of Zürich

 
 

Research

The applied algebra group is mainly involved in research questions coming from coding theory and cryptography.

Coding Theory

Coding theory has emerged out of the need for better communication and computer data storage and has rapidly developed as a mathematical theory in strong relationship with algebra, combinatorics and algebraic geometry.

We have been involved into the study of two main areas of coding theory:

Construction of LDPC Codes and more general codes on graphs

In recent years there have been some exciting developments. First and foremost it has been realized that error coding techniques near the Shannon limit should become practical in the foreseeable future using graph-based code designs. It began with the discovery of turbo codes in 1993 and the subsequent "re-discovery'' of low density parity check (LDPC) codes.

In collaboration with the coding group at the University of Notre Dame we were involved in new algebraic constructions of "Codes on Graphs'' having moderate block length and which perform as well or better than comparable randomly generated codes.

The Research on LDPC codes was supported by the US National Science Foundation under grant #0205310 and by the Swiss National Science Foundation under grant #113251

 

Construction of Convolutional Codes

Convolutional codes are used in the data transmission of many communication systems. Convolutional codes can be viewed as linear systems over a finite field. The study of these codes requires a good understanding of the algebraic representation of linear systems.

The project addresses a number of issues in mathematical systems theory and in coding theory. The main objectives are:

  1. New methods for constructing convolutional codes with a large free distance and a relatively small degree.
  2. New techniques to tackle the decoding problem of convolutional codes in an algebraic manner.

The Research in convolutional coding theory has been supported by the US National Science Foundation under grant #0072383. Some of this research is nowadays of immense importance in the area of video and more general multimedia streaming. (See e.g. ) .

 

Network Codes

Network coding theory is concerned with the encoding and transmission of information where there may be many information sources and possibly many receivers. The applied algebra group is mainly concernedwith the construction and the decoding of so called subspace codes.

The research is related and supported by a European COST action project .

 The Swiss National Science Foundation supported this research under grants #126948, #138080  #149716 and currently supports the research under grant #169510

 

Cryptography

This main focus of our research is concerned with the creation and the study of new one-way trapdoor functions. This would ultimately lead to the construction of new public-key cryptosystems which could still exist in case that a quantum computer could be built which is capableof doing large scale computations. For this compare with the Dimacs workshop on The Mathematics of Post-Quantum Cryptography.

The study of one-way trapdoor functions is interesting both from a theoretical and from a practical point of view. From a theoretical point of view, our research involves techniques from different parts of algebra and geometry, such as the theory of finite rings, the theory of semigroups and loops, and arithmetic algebraic geometry. 

From the point of view of applications, this research could lead to new cryptographic protocols of potential interest to industry and government.

 

The Swiss National Science Foundation supported this research under grants #107887 and #132256 and the research is currently supported by a grant from the Armasuisse.