"Sjølv etter årevis med forsking veit du ofte ikkje kvar du endar opp."

Korleis enda du opp som informatikar?

Informatikk var på ingen måte eit opplagt val. Eg var interessert i både litteratur og historie, og som musikkentusiast verka det meir freistande å bli rockestjerne. Men eg var god i matematikk, og sidan matematikkfakultetet berre var ein tjue minutt lang spasertur frå huset mitt, bestemte eg meg for å melde meg opp der.

Interessa mi for matematikk utvikla seg gradvis til ei lidenskap for algoritmar, som etter kvart blei ein karriere innan informatikk.

Når du arbeider med eit problem, vil det – anten du lukkast eller ikkje – leie deg til eit nytt problem. Det er både avhengnadsskapande og uføreseieleg; sjølv etter årevis med forsking veit du ofte ikkje kvar du endar opp.

Kva for problem arbeider du med no?

Mesteparten av forskinga mi handlar om korleis ein systematisk kan klassifisere rekneproblem basert på den ibuande kompleksiteten deira, og deretter lage algoritmar som utnyttar spesifikke strukturar for å løyse desse problema meir effektivt.

For å seie det svært enkelt: I informatikk betyr ibuande kompleksitet (intrinsic complexity) kor vanskeleg det er å utføre ei oppgåve. Oppgåver kan vere vanskelege på ulike måtar. Om ein veit kva som gjer ei oppgåva vanskeleg, kan ein endre metoden for å løyse ho meir effektivt.

Med moderne algoritmeutviklingar har det blitt tydeleg at worst-case time complexity ofte ikkje klarer å føresei korleis algoritmar fungerer i røynda.

Kva er utfordringane innan algoritmeteori?

Det er usemje mellom korleis forskarar vurderer algoritmar på teoretisk nivå og korleis algoritmar fungerer i praksis. Mange algoritmar som er teoretisk sett vanskelege, fungerer faktisk veldig godt i praksis.

Dette kjem av at informatikkforskarar er styrte av pessimisme – eller som dei sjølve kallar det: «Worst-case time complexity»

Algoritmar blir ofte vurderte ut frå kor mykje arbeid datamaskina må gjere, og worst-case time complexity er ein måte å måle ein algoritme ut frå det verstefalls-scenarioet – altså den lengste tida den kan kome til å bruke.

Med moderne algoritmeutviklingar har det blitt tydeleg at worst-case time complexity ofte ikkje klarer å føresei korleis algoritmar fungerer i røynda.

Til dømes, innan maskinlæring er nesten alle modellane som brukast rutinemessig og fungerer godt i praksis, rekna som dårlege utifrå worst-case time complexity.

I helsesektoren kan algoritmar brukast til å analysere MR-bilete. I teorien er dette ei oppgåve datamaskiner burde svært dårlege på. Men i røynda kan datamaskiner likevel identifisere ulike typar vev i kroppen og oppdage avvik som arrvev eller kreft med høg presisjon.

Dette avslører ein betrakteleg sprekk mellom forståinga av rekning og algoritmar. Det vi antek frå worst-case time complexity samsvarer ofte ikkje med korleis algoritmar faktisk presterer. Etter mi meining er det å redusere denne sprekken den største utfordringa innan algoritmeteori i dag.