Skip to main content

Wictor Zawadzki: RNG and Derandomized Algorithms

BSc Thesis Presentation

Time: Fri 2020-08-28 09.30 - 10.30

Location: Zoom, meeting ID: 63598179403

Participating: Wictor Zawadzki

Supervisor: Olof Sisask

Export to calendar

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.