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.