Randomness in complexity theory and logics [Elektronische Ressource] / Kord Eickmeyer. Gutachter: Martin Grohe ; Nicole Schweikardt ; Peter Bro Miltersen

Randomness in Complexity Theory and LogicsDISSERTATIONzur Erlangung des akademischen Gradesdoctor rerum naturaliumim Fach Informatikeingereicht an derMathematisch-Naturwissenschaftlichen Fakultät IIHumboldt-Universität zu BerlinvonDipl.-Math. Kord Eickmeyer20.08.1979, Lage, GermanyPräsident der Humboldt-Universität zu Berlin:Prof. Dr. Jan-Hendrik OlbertzDekan der Mathematisch-Naturwissenschaftlichen Fakultät II:Prof. Dr. Elmar KulkeGutachter:1. Prof. Dr. Martin Grohe2. Prof. Dr. Nicole Schweikardt3. Prof. Dr. Peter Bro MiltersenTag der mündlichen Prüfung: 29. August 2011AbstractThis thesis is comprised of two main parts whose common theme is the question ofhowpowerfulrandomnessasacomputationalresourceis. Inthefirstpart(chapter2)we deal with random structures such as graphs or families of functions and explainhow these can possess – with high probability – properties than can be exploitedby computer algorithms. Though it may seem counterintuitive at first, it can bevery hard to deterministically construct a structure (such as a graph) possessingsome desirable property such as good expansion which a random structure has withhigh probability.