Search games with lies and data transmission models with errors

Dr. Christian Deppe

Bielefeld University, Bielefeld

Abstract:

The Renyi-Berlekamp-Ulam game is a classic model for the problem of determining the minimum number of queries to find an unknown member in a finite set when up to a finite number of the answers may be erroneous. In the context of the theory of error-correcting codes, our searching strategies are the same as error-correcting codes for the noiseless delayless feedback channel.

In this presentation, I present the classic model and different variations with solutions. To some of these models there are so far no solutions. An interesting open problem is, for example, the proof or disproof of our conjecture to the q-ary case of the rate function of the Renyi-Berlekamp-Ulam problem.

Biography:

Christian Deppe received the Dipl.-Math. degree in mathematics from the Bielefeld University in 1996, and the Dr.-Math. degree in mathematics from the same university in 1998. He was a Research and Teaching Assistant in the Department of Mathematics at the Bielefeld University from 1998 to 2010. From 2011 to 2013 he was project leader of the project ``Sicherheit und Robustheit des Quanten-Repeaters´´ of the Federal Ministry of Education and Research in the Department of Mathematics at the Bielefeld University.
In 2014 he was supported by a DFG project at the Institute of Theoretical Information Technology at the Technical University of Munich. In 2015 he had a temporary professorship in the Department of Mathematics and Informatics at the Friedrich-Schiller University in Jena. He is currently project leader of the project ``Abhörsichere Kommunikation über Quanten-Repeater´´ of the Federal Ministry of Education and Research in the Department of Mathematics at the Bielefeld University.