Gennem min tid som ph.d.-studerende har jeg udgivet artikler inden for to forskningsfelter, hvilket afspejles i denne afhandling. Dagens menu består således af såkaldte Johnson--Lindenstrauss-transformationer som hovedret efterfulgt af kredsløbsnedergrænser for udregning af heltalsprodukter til dessert. Vinen står De selv for.
Afhandlingen introducerer først Johnson--Lindenstrauss-transformationer og fastslår deres centrale plads som grundstenen i flere successrige dimensionsreduktionskonstruktioner, hvorefter den gennemgår den historiske udvikling, der er sket inden for feltet, siden Johnson og Lindenstrauss udgav deres artikel i 1984. Dette efterfølges af analyser af de to hovedstrømninger inden for Johnson--Lindenstrauss-transformationer eksemplificeret ved en tæt nedergrænse for Toeplitz-konstruktionen samt en præcis ydeevnesammenhæng for den praksisorienterede feature hashing-konstruktion (egenskabsfordelingskonstruktionen).
Ud over selve nedergrænserne og sammenhængene fremviser denne afhandling også de nyttige bevisteknikker, der banede vej til resultaterne, og som bygger på centrale sandsynlighedsteoretiske sætninger samt sammenkoblinger mellem tilfældig realtals-lineær algebra og diskrete kombinatoriske grafproblemer. Disse bevisteknikker viser sig som værdifulde værktøjer, der vil være enhver teoretiker værdig, hvis vedkommende vil erhverve sig en dybere forståelse af disse anerkendte og aldeles anvendelige algoritmer.
Efter at have nydt en fyldig tallerken med lineær algebra og sandsynlighedsteori, venter der en forfriskende lækkerbisken af kredsløbsnedergrænser.
Heltalsproduktsudregning er en af de mest fundamentale og mest anvendte operationer udført af datamater i dag, men det er samtidig ukendt, hvor effektivt det kan beregnes. Selv spørgsmål såsom: ``Er heltalsprodukter fundamentalt sværere at udregne end heltalssummer?'' virker uden for vores rækkevidde. Denne afhandling bringer os meget tættere på et svar, idet den viser, at antaget en central konjektur inden for netværkskodningsteori er heltalsprodukter signifikant sværere at udregne end heltalssummer, samt at vores nuværende bedste heltalsproduktudregningskredsløb er optimale. Endvidere relaterer afhandlingen også konjekturen fra netværkskodningsteorien til generelle og mangeårige konjekturer inden for kredsløbskompleksitet.