Action IC1104

Chairs: Tuvi Etzion, Joachim Rosenthal

Traditional algebraic coding theory is aware of a number of existence bounds for linear and non-linear error-correcting codes. Among the restrictive examples of bounds, one has to mention the Plotkin and Elias-Bassalygo bound, the sphere-packing bound, the Singleton bound, whereas bounds like the Gilbert-Varshamov bound and the BCH-bound are assertive and often provide construction mechanisms for good codes. This Working Group will focus on the mathematical task to formulate and prove amended versions of traditional bounds, or to provide new bounds for network codes. From possible assertive bounds it is expected that new construction methods will be provided to the benefit of the work in Working Group 4.

Chair: Ángeles Vázquez-Castro

As in traditional coding theory, practicability of a network code results from the question if there are efficient encoding and decoding schemes. Whereas encoding is usually an efficient task for algebraically induced structures, decoding is a highly non-trivial task as it is not simply the reverse of encoding but also comprises the correction of the erasures or erroneous insertions that have occurred during transmission. This task is devoted to the computer science/engineering endeavour of designing efficient algorithms and will be influenced by the results introduced in the work of Working Group 4.

Network coding has a strong application potential for information transmission over data networks and different aspects of network coding have already been tested and implemented across various layers of standard protocol stacks. For example, analog network coding has been intensively researched for applications at the physical layer of wireless communication systems, opportunistic MAC-level network coding such as COPE protocol developed by MIT is relevant in Wi-Fi applications, and network coding over data packets at application layer is proposed and demonstrated by Microsoft in peer-to-peer (P2P) data exchange system Avalanche as well as for practical multimedia streaming on smartphones. The task of this working group is to further progress with the applied random network coding research as welI as to investigate application potential in subspace coding in similar or novel applications. In this sense, the results in Working Group 5 related to code designs for distributed storage will also be relevant to this working group.

Chair: Simon Blackburn

The security of network coding is a vitally important issue. It is closely interrelated, but is separate from, the issues surrounding efficient and reliable network coding. In fact, the design of a secure network coding scheme is a challenge of new nature, with the presence of the intermediate nodes leading to wiretap attacks or pollution attacks that are not considered in most standard cryptographic security models. During recent years, solutions have been proposed based on homomorphic hashing and homomorphic signatures. The work on this aspect of the project spans theoretical computer science and mathematics, with techniques from areas such as public key cryptography, protocol design, and secret sharing being relevant.

Chairs: Tuvi Etzion, Joachim Rosenthal

Traditional coding theory is aware of two different construction issues, one of them a purely practical, where the other being more theoretical and particularly touching asymptotic aspects of coding. The former type of construction is interested in codes of small size and small length that come with efficient encoders and decoders and are ready for implementation in communication devices. The latter focuses on the existence of infinite families of codes for which information rate and error-correction capabilities are clearly bounded away from zero. Particularly in search of good network codes of relatively small size in small projective geometries intelligent searches based on assumptions on the inner symmetry of the code can significantly help the construction process. This task is of highly mathematical nature and requires strong computational power for the resulting searches. Judging the quality of its outcomes will require results from Working Group 1.

Chair: Camilla Hollanti

Aspects of code equivalence, distance distribution and the like are important for classification and comparison of given network codes. These are in particular applied to network codes for distributed storage. They provide powerful theoretical tools that facilitate successful work in Working Group 1 to 4. The questions are of mathematical nature and significantly impact the research field.