Dissertation in the field of Information Theory, Ashik Mathew Kizhakkepallathu

The title of thesis is Combinatorial Algorithms for Packings, Coverings and Tilings of Hypercubes

A vast number of engineering and everyday problems are packing and covering problems. Transport companies want to pack goods in containers as efficiently as possible, and the family going on a car holiday faces a similar challenge. Operators want as good coverage as possible for their mobile networks. Indeed, many problems in telecommunications and its supporting field of information theory can mathematically be phrased in these settings. In particular this applies to the issue of transmitting information fast and without errors; the related concepts in telecommunications are capacity and error-correction.

The capacity problem plays a central role in the current work. Many of the mathematical structures involved are high-dimensional cubes and similar mathematical objects. Most of the techniques used are computer-aided and several years of single-core computer time (often days on a supercomputing cluster) was required to obtain some of the results. Symmetries are important in some of the work. One of the major open problems in information theory is that of determining the capacity of (a communication channel that can be modeled via) a cycle of odd length. The Hungarian mathematician László Lovász determined the capacity of a cycle of length 5 in a groundbreaking work published in 1979. In this thesis, among other things a new bound on the capacity of a cycle of length 7, the next open case, is obtained. This is the first progress on that problem in over a decade.

Opponent: Professor Sándor Szabó, University of Pécs, Hungary

Supervisor: Professor Patric R. J. Östergård, Aalto University School of Electrical Engineering, Department of Communications and Networking