DS0704 - Fondements du numérique

Randomness and Computability : Advancing the Frontiers – RaCAF

Submission summary

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.

Project coordination

Alexander Shen (Laboratoire d'Informatique Robotique et Microélectronique de Montpellier)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


LIX Laboratoire d'Informatique de l'Ecole Polytechnique
CNRS-LIRMM Laboratoire d'Informatique Robotique et Microélectronique de Montpellier

Help of the ANR 402,005 euros
Beginning and duration of the scientific project: September 2015 - 48 Months

Useful links

Explorez notre base de projets financés



ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter