Wictor Zawadzki: RNG and Derandomized Algorithms
BSc Thesis Presentation
Tid: Fr 2020-08-28 kl 09.30 - 10.30
Plats: Zoom, meeting ID: 63598179403
Medverkande: Wictor Zawadzki
Handledare: Olof Sisask
Abstract
Randomness is heavily relied upon in different computation situations across many industries, but generating a lot of random numbers can be quite resource intensive. As a result, an argument could be made in favor of derandomizing algorithms into deterministic form whenever possible.
The goal of this thesis is to investigate random number generation, and the use of randomness in algorithms. We first look at theoretical construction of pseudo-random number generators, statistical tests, and cryptographic random number generators, as well as some practical examples for these. The second part of the thesis focuses on the differences in method and performance between random algorithms and their derandomized counterparts.
After looking at specific random algorithms, we conclude in this thesis that deterministic algorithms seem to often suffer a few disadvantages from not using random numbers. Two examples of significant drawbacks are the existence of pathological inputs, as well as that some algorithms may fundamentally require randomness to function as intended, for instance cryptographic systems.