Discrete Structures in Combinatorics, Information Theory and the Theory of Algorithms

• Applicant: Professor Dr. Michael Huber
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2007 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 39993490

• Final Report Year: 2013

Final Report Abstract

This project within the DFG Heisenberg program is concerned with the fundamental role of discrete structures and their applications in several key areas of current research in combinatorics, information theory and cryptography / coding, the theory of algorithms and bioinformatics. Specific tasks of research range from mathematical studies on combinatorial designs and related objects – through interactions with structural algorithmic questions related to iterative and majority-logic decoding for error-correcting codes, graph isomorphism testing as well as group testing algorithms in DNA screening – to studies of their interrelationship for effective code design, such as for authentication and secrecy codes or low-density parity-check codes. The topics are of broad academic interest and offer substantial real-world application potential. By combining the strengths of diverse methods and tools from discrete mathematics and theoretical computer science, significant progress on these challenging research problems have been achieved. Some highlights are a) the design of various novel authentication and secrecy codes addressing the very timely topic of how to construct codes that ensure confidentiality, authentication or both in the sense of information-theoretic security and hence offer in fact quantum computer attack-resistance; b) newly constructed low-density parity-check codes that are of increasing practical importance, for instance in high-speed applications in magnetic recording and optical communications channels, as they exhibit performance near the Shannon capacity limit; c) efficient majority-logic decoding of error-correcting codes that is of special usefulness for safety- and time-critical applications in embedded systems such as airbag systems, anti-lock braking systems (ABS) or medical systems like heart pacemakers; d) innovative and efficient group testing algorithms that are particularly suited for rapid and lessexpensive DNA library screening and other large scale biological group testing efforts; e) a new framework for dimension reduction methods within an visual analytics pipeline to detect important biological signals in systems biology data, in particular in high-dimensional expression data. The Principal Investigator is convinced that the new approaches and techniques resulting from this project will lead to new developments in combinatorics, information theory, the theory of algorithms, bioinformatics as well as in other domains. In particular, the investigations offer, beyond answering profound scientific questions, a high innovation potential for applications in future information and communication systems.

Publications

• Combinatorial Designs for Authentication and Secrecy Codes. Foundations and Trends in Communications and Information Theory, Now Publishers, Boston, Delft, 2010
  M. Huber
  
• Computational complexity of reconstruction and isomorphism testing for designs and line graphs. Journal of Combinatorial Theory, Series A, Vol. 118, pp. 341–349, Elsevier, 2011
  M. Huber
  
• New combinatorial construction techniques for low-density paritycheck codes and systematic repeat-accumulate codes. IEEE Transactions on Communications, Vol. 60, pp. 2387–2395, IEEE Press, Piscataway, NJ, 2012
  A. Gruner and M. Huber
  
• Perfect secrecy systems immune to spoofing attacks. International Journal of Information Security, Vol. 11, pp. 281–289, Springer, 2012
  M. Huber
  
• Efficient majority-logic decoding of short-length Reed–Muller codes at information positions. IEEE Transactions on Communications, Vol. 61, pp. 930–938, IEEE Press, Piscataway, NJ, 2013
  P. Hauck, M. Huber, J. Bertram, D. Brauchle, and S. Ziesche
  
• Efficient two-stage group testing algorithms for genetic screening. Algorithmica, Vol. 67, pp. 355–367, Springer, 2013
  M. Huber
  
• Low-density parity-check codes from transversal designs with improved stopping set distributions. IEEE Transactions on Communications, Vol. 61, pp. 2190– 2200, IEEE Press, Piscataway, NJ, 2013
  A. Gruner and M. Huber
  
• Visualizing dimensionality reduction of systems biology data. Data Mining and Knowledge Discovery, Vol. 27, pp. 146–165, Springer, 2013
  A. Lehrmann, M. Huber, A.C. Polatkan, A. Pritzkau, and K. Nieselt