Randomness and Computability : Advancing the Frontiers – RaCAF

Random sequences are essential for modern computer science. They are used for security and cryptography purposes and are at the heart of randomized algorithms. In practice, pseudo-random sequences are used. The impact of their inherent regularities can be problematic depending on the context. To better understand this deficiency, one needs to study the links between computation and randomness. Randomness being a limit-notion of computation, we propose to study computation models with enhanced capabilities (involving infinite time computations or using real urelements). For a number years now, physicists have been building 'perfect' random number generators based on quantum phenomena, using secret algorithmics post-processes which seem to jeopardize the purity of the random numbers. We propose to analyse these sequences by using complex algorithmic methods based on our theoretical research and on randomized algorithmic constructions.