Challenging Applications of Randomness

The main research focus of our group is on understanding random discrete structures. This includes various aspects, from developing randomized algorithms over analyzing games all the way to proving results on methods and tools for handling random structures. All this research is of foundational nature, i.e., we usually do not have any concrete 'real-world' application in mind. While this kind of research is close to our heart and forms our daily business, we also, once in while, like to show how useful our way of thinking - and our understanding of random structures - is for attacking problems that come from 'real' applications.

2000-2003: E-Jigsaw

In 1989 the "Ministerium für Staatssicherheit" of the former German Democratic Republic tried to destroy all documents containing inculpatory material. A majority of the documents was torn by hand only and the pieces later recovered. Those pieces are now stored in archives of the Bundesbehörde für die Unterlagen des Staatssicherheitsdienstes der ehemaligen DDR: there exist approximately 17.000 bags each containing about 2.000 torn documents. In the early 90ies the Germany government started a project of reconstructing the pages by hand, a gigantic jigsaw puzzle. When we started our project, only 300  out of the 17000 bags were reconstructed.

We had the idea to develop a prototype of a software system for solving this problem. We pursued this project as a student project (at TU München). Our main idea for attacking this problem was that tearing papers apart by hand leads to quite unique edges and that an efficient characterization of these edges can subsequently be used to speed up the reconstruction process significantly. We presented our prototype solution to the public on May 20, 2003. This created a lot of echo in the German press - and eventually resulted in an automized reconstruction process for the original data.

More details of our project can be found on our original project web page (in German).

Since 2007: On the Use of Randomness in Neuroscience

For every engineer it goes without saying: in order to build a reliable system we need components that consistently behave precisely as they should. But then: why can our brain do so many amazing things? Neuroscientists know very well that neurons, the building blocks of brains, come with huge variances in their properties and that these properties also vary over time. Synapses, the connections between neurons, are known to be highly unreliable in forwarding signals: some 40%-80% percent of the time they simply ignore the incoming signal instead of forwarding it. Is this a 'bug' or a 'feature'? We do not know. Yet. As we, the research community, do not really have a good clue of how our brain 'computes'.

Our goal in this project is to provide indications that randomness in the brain is actually not a 'deficiency' that needs to be overcome, but that, quite to the contrary, this randomness is in fact essential for many of the nice features that our brains exhibit.

Reliable neuronal systems: the importance of heterogeneity
J. Lengler, F. Jug, and A. Steger
PLOS ONE, December 2013.