´

Integer Linear Programming Models for Subspace Codes and Finite Geometry
(Ganzzahlige Optimierungsmodelle für Subspace Codes und endliche Geometrie)
KU 2430/3-1, WA 1666/9-1

Fano_plane.svg

Description

Error-correcting codes are employed in almost every form of information transmission and storage. Well known examples include communication with space probes, Digital TV (DVB), ADSL, distributed storage systems (Windows Azure) and CD player.

Numerous applications in communication networks such as the Internet, mobile devices like smartphones and cloud computing, with its rapidly changing technical standards, require a mathematical theory that is independent of the exact network topology. In the prevailing model of communication a (finite) projective geometry, i.e. the set of all subspaces of a finite vector space, functions as an alphabet.

A subspace code is a subset of a given projective geometry. One major research direction is the question of existence and construction of good or even optimal subspace codes. A comprehensive search of subspace codes will be performed, that is, all reachable sets of parameters should be systematically searched for good subspace codes.

The construction methods previously applied in the Bayreuth research group using prescribing a subgroup of the automorphism group, will be used intensively in order to reduce the search space to a convenient size. The underlying idea is to formulate the problem as an integer linear system of equations. This description fits well with the conditions of automorphisms, since it massively reduces both, the number of variables and the number of constraints. There is reason to hope that subspace codes with good properties have some automorphisms.

As an innovation, sharper integer formulations shall be found. The basic idea here is to use results and substructures of finite geometry on vector spaces. From an algorithmic point of view, some of the arguments used there correspond to adding feasible inequalities or Gomory-Chvátal cutting planes. The main idea here is to model and enumerate geometric structures, such as holes, cuts, or regulus, and the use of methods of integer linear optimization.

This project is funded by the Deutsche Forschungsgemeinschaft. Details can be found on the sites of the DFG.

Supported by

dfg_logo

Project Leader

Duration of the Project

April 2015 - March 2018

Team Members

events / teaching

literature

2019

2018

2017

2016

2015

2014

2013

2012

Homepage

A table with subspace codes: http://subspacecodes.uni-bayreuth.de.

University of Bayreuth -