Emin Karayel - Derandomization with Pseudorandomness

afm:13477 - Annals of Formalized Mathematics, July 15, 2025, Volume 1 - https://doi.org/10.46298/afm.13477
Derandomization with PseudorandomnessArticle

Authors: Emin Karayel

    Derandomization techniques are often used within advanced randomized algorithms. In particular, pseudorandom objects, such as hash families and expander graphs, are key components of such algorithms, but their verification presents a challenge. This work shows how such algorithms can be expressed and verified in Isabelle and presents a pseudorandom objects library that abstracts away the deep algebraic/analytic results involved. Moreover, it presents examples that show how the library eases and enables the verification of advanced randomized algorithms. Highlighting the value of this framework is that it was recently used to verify the space-optimal distinct elements algorithm by Blasiok from 2018, which relies on the combination of many derandomization techniques to achieve its optimality.


    Volume: Volume 1
    Published on: July 15, 2025
    Accepted on: May 13, 2025
    Submitted on: April 26, 2024
    Keywords: Logic in Computer Science,03B35, 68W20,G.3; F.4.1