Doktorand i Teoretisk datavetenskap (algoritmer och komplexitet)

KTH svarar för en tredjedel av Sveriges kapacitet av teknisk forskning och ingenjörsutbildning på högskolenivå. Utbildningen och forskningen täcker ett brett område – från naturvetenskap till alla grenar inom tekniken samt arkitektur, industriell ekonomi och samhällsplanering. Totalt finns vid KTH mer än 14000 studenter på grundnivå och avancerad nivå och över 1700 forskarstuderande. KTH har nästan 4600 anställda.

Skolan för Datavetenskap och kommunikation är en av Sveriges mest framstående forsknings- och undervisningsmiljöer inom informationsteknologi med verksamhet på KTH och delvis även på Stockholms universitet. Vi bedriver utbildning och forskning inom både teoretisk och tillämpad datalogi. Den teoretiska datalogin sträcker sig från teoribildning och analys av matematiska modeller via algoritmutveckling till implementation och simulering.
Den tillämpade datalogiska forskningen och utbildningen omfattar datorseende, robotik, maskininlärning, högprestandaberäkningar, visualisering, beräkningsbiologi, neuroinformatik och neurala nätverk, samt tal- och musikkommunikation. Dessutom bedrivs tillämpad forskning och utbildning inom medieteknik, människa-datorinteraktion, interaktionsdesign och hållbar utveckling.
Mer information om CSC finns på www.kth.se/csc

ARBETSUPPGIFTER
KTH Datavetenskap och kommunikation (CSC) söker en doktorand i Teoretisk datavetenskap (algoritmer och komplexitet).

Inom teoretisk datalogi studeras grunderna för effektiva och korrekta algoritmer, och man söker förstå vilka beräkningsproblem som kan lösas effektivt. Tillämpningar finns bl a inom beräkningsbiologi, kryptografi, språkteknik och komplexa tekniska system. Många viktiga beräkningsproblem är NP-svåra, vilket innebär att det är osannolikt att de kan lösas i polynomiell tid.

En ansats för att handskas med NP-svåra problem som blomstrat de senaste decennierna är att studera hur bra approximativa lösningar kan hittas effektivt. För många fundamentala problem som t.ex. maximal klick och maximalt snitt har vi nu en väldigt god förståelse för hur bra de kan approximeras i polynomiell tid. En annan ansats är att utveckla snabbare exakta algoritmer för dessa problem. Även om det är troligt att sådana algoritmer kräver exponentiell tid så har storleken på den exponentiella tillväxten stor betydelse för hur stora probleminstanser som kan lösas. De senaste åren har snabbare algoritmer upptäckts för fundamentala problem som t.ex. graffärgning och hamiltonicitet.

De här två ansatserna är i någon mening två extrema exempel på hur man kan handskas med NP-svåra problem. För många problem är den bästa approximationsalgoritmen förvisso snabb men ger inte tillräckligt bra lösningar, och den snabbaste exakta algoritmen för långsam för att lösa intressanta probleminstanser. Målet i det här projektet är att undersöka vilka avvägningar som är möjliga mellan dessa två extremer. Projektet leds av Per Austrin och finansieras av ett projektanslag från Vetenskapsrådet.

KVALIFIKATIONER
Exempel på lämplig bakgrund för tjänsten är civilingenjörsexamen eller motsvarande inom datavetenskap, teknisk fysik, eller liknande. Den blivande doktoranden förväntas ha en stark bakgrund och stort intresse för teoretisk datavetnskap (algoritmer och komplexitet) och matematik (föredragsvis områden som kombinatorik, sannolikhetsteori, och/eller diskret analys). Starka kandidater är alltid av intresse oavsett formell bakgrund. Problemlösningsförmåga och kreativitet är ett måste. Praktisk programmeringsfärdighet är en fördel.

Sökande skall vara starkt motiverad för forskarstudier, ha förmåga till självständigt arbete och kritisk analys samt god samarbets- och kommunikationsförmåga. Mycket goda kunskaper i engelska i tal och skrift är en förutsättning för att kunna medverka i projektets internationella samarbeten och för att publicera och presentera forskningsresultat i internationella konferenser och tidskrifter.