Meltzerpris til Daniel Lokshtanov
Daniel Lokshtanov ved Institutt for informatikk er tildelt den prestisjetunge Meltzerprisen for yngre forskere.
Hovedinnhold
Årets Meltzerpriser ble delt ut under den tradisjonelle Meltzermiddagen, mandag 8. mars. Lokshtanov er en av fire prisvinnere.
Daniel Lokshtanov er født i 1984 i Moskva. Han får Meltzerprisen for sitt banebrytende bidrag til et nytt og raskt voksende felt innen informatikk – datareduksjon som hjelpemiddel til å løse vanskelige beregningsproblemer. Daniel Lokshtanov fullførte mastergraden ved Universitetet i Bergen i 2006, etter bare tre års studier. I juni 2009 disputerte Lokhstanov for ph.d.-graden, et år før normert tid. Lokhtanov har produsert mer enn 40 vitenskapelige artikler, alle på høyt internasjonalt nivå.
For mange viktige beregningsproblemer er den beste kjente løsningsmetoden essensielt å prøve alle muligheter. Dette er ekstremt tidkrevende selv for moderate størrelser av inndata. Imidlertid er det ofte mulig å ”rydde” inndata for irrelevante elementer før man prøver alle muligheter, og slike løsningsmetoder er ofte effektive i praksis.
I sin doktoravhandling har Daniel Lokshtanov vært med på å utvikle en matematisk modell for å studere datareduksjon. Han viser at effektiv datareduksjon er mulig for nesten alle tenkelige problemer dersom inndata er ”glissent”, noe som er tilfelle dersom inndata stammer fra for eksempel kart over veier, rørnettverk eller skjema for elektriske kretskort. Han utvikler også metoder for å vise at datereduksjon i enkelte tilfeller simpelthen ikke er mulig, og bruker disse metodene til å vise at to problemer som ved første øyekast ser nesten like ut oppfører seg svært forskjellig.
Matematisk analyse av datareduksjon har fått mye oppmerksomhet i løpet av de siste tre årene, og resultatene i Lokhtanovs avhandling har vært med på å løfte feltet til et helt annet nivå enn der det var for få år siden.
Kontakt: Daniel Lokshtanov, tlf 95 20 23 09
Meltzerprisene 2009:
