Browsing by Author "Saarhelo, Joonatan"

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • Fast and Correct Round Elimination
    (2022-07-29) Saarhelo, Joonatan
     Perustieteiden korkeakoulu | Master's thesis
    Round elimination is a process used to study the hardness of distributed graph problems. It is available as a computer program. Optimizations to the program have permitted the study of more complex problems. Because no fast algorithm for checking the result of round elimination is known, it must be implemented correctly. In this thesis I present a new algorithm for maximization, the most computationally expensive part of the original Round Eliminator, prove that the new algorithm is asymptotically faster and formally verify the theory behind it in Coq along with a program that checks maximization results using the new algorithm. An implementation based on the new algorithm makes round elimination orders of magnitude faster in practice. Unfortunately, the verified checker is too slow for practical use but that is not a fundamental limitation, only a flaw in the particular way it was written.
  • Supercompilation of purely functional programs
    (2017-12-20) Saarhelo, Joonatan
     Perustieteiden korkeakoulu | Bachelor's thesis