NY DOKTORGRAD
Hvor vanskelig kan det være?
 Foto: Eivind Senneset |
"Tournaments and optimality: new results in fixed-parameter tractability".
Datamaskiner hjelper oss med å løse en rekke problemer i hverdagen, og på daglig basis trenger vi å analysere hvor vanskelige de ulike problemene er. Moderne analysemetoder handler ikke bare om å designe raskest mulig algoritmer, men også om å forstå hvor mye ressurser, som tid og minne, som virkelig trengs for å løse et bestemt problem. Ofte er vi i den heldige situasjonen at kunnskap om ulike begrensninger rundt inndata kan hjelpe oss med å finne raskere algoritmer. Det kan for eksempel være at inndata har ønskelige egenskaper, eller at løsningen vi leter etter er liten i størrelse. En måte å formalisere slike spørsmål på er gjennom et paradigme som heter parametrisert kompleksitet, og avhandlingen konsentrerer seg om metoder innen dette paradigmet.
Pilipczuk studerer i første delen av avhandlingen problem tilknyttet spørsmålet om innhold: gitt to strukturer, en liten og en stor, er den første inneholdt i den andre? Svaret på dette avhenger av ulike definisjoner av innhold. Pilipczuk beskriver en matematisk innholdsteori for en mengde velkjente strukturer, kalt turneringer. En direkte konsekvens av denne teorien er at vi nå kan finne algoritmer for mange innholdsproblem som gjelder turneringer, mye raskere enn de vi har kjent til tidligere.
I del nummer to ser Pilipczuk på problemene rundt det å finne skjulte egenskaper i enkelte strukturer. Spesielt konsentrerer han seg om å finne de egenskapene som ikke ligger spesielt dypt så raskt som mulig. For å dra en parallell til noe vi kjenner bedre kan en se på det som å identifisere dyrearter: vi har fått en del observasjoner av dyr, sammen med informasjon om hvilke dyr som ligner hverandre. Noe av denne informasjonen kan være feil, og vi vil finne disse, for å bedre kunne finne ut hvilke dyr som tilhører samme art. For slike problem gir avhandlingen algoritmer som er beviselig optimale i den forstand at eksistensen av bedre algoritmer ville føre til meget uventete konsekvenser i kompleksitetsteori.
Personalia:
Michał Pilipczuk er født i 1988 i Warszawa, Polen. Han fikk sin mastergrad i informatikk i 2011 og i matematikk i 2013, begge fra Universitetet i Warszawa. Siden september 2011 har han vært ansatt som stipendiat ved Institutt for informatikk, under ERC-prosjektet, ledet av hans veileder, Professor Fedor Fomin. Pilipczuk gjør ferdig sin ph.d.-grad to år tidligere enn normert, og vil fortsette som stipendiat ved Institutt for informatikk.
Tidspunkt og sted for prøveforelesningen:
26.09.2013, kl. 10.15. Oppgitt emne: "Expander graphs and their applications".
Sted: Høyteknologisenteret, Datablokken, 2.etg, Lille Auditorium.
Tidspunkt og sted for disputasen:
22.11.2013, kl. 14.00, Høyteknologisenteret, Datablokken, 2.etg, Store Auditorium.
Kontaktpersoner:
Michał Pilipczuk, tlf. 55 58 42 94, e-post: michal.pilipczuk@ii.uib.no
Mediekontakt ved Kommunikasjonsavdelingen
E-post: mediekontakt[ætt]uib.no
Telefon: 55 58 89 00
Avhandlingen kan lånes på Bibliotek for realfag. Avhandlingen er tilgjengelig i BORA. For kjøp/bestilling av avhandlingen, kontakt kandidaten direkte.