Forsker ved IT-Universitetet vinder en af verdens mest prestigefyldte priser inden for teoretisk datalogi
Lektor ved IT-Universitetet i København, Nutan Limaye, er medforfatter på en forskningsartikel, som har vundet Best Paper Award på Foundations of Computer Science’s (FOCS) IEEE Symposium. Det er første gang, at forskere ved et dansk universitet vinder prisen.
ForskningInstitut for Datalogialgoritmerpriser
Forskningsartiklen, Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits, er blevet kåret som den bedste på Foundations of Computer Science’s (FOCS) årlige IEEE Symposium. Det er lektor ved IT-Universitetet i København, Nutan Limaye, som har skrevet artiklen sammen med Srikanth Srinivasan (Aarhus Universitet) og Sébastien Tavenas (LAMA, Université Savoie Mont Blanc).
Resultaterne i forskningsartiklen er et skridt i retning af at forstå svaret på et af de klassiske tusindårsspørgsmål inden for beregningskompleksitet, nemlig spørgsmålet om P versus NP. I årtier har forskere kæmpet med at finde svaret på spørgsmålet, som kort fortalt handler om at forstå computernes begrænsninger og selve beregningskompleksitetens natur. Beregningskompleksitet er grundlæggende for stort al algoritmeforskning og har fx indflydelse på vores tillid til kryptografiske systemer (som vi vil have bevis for sikkerheden af) samt dagligdagsværktøjer som fx navigations-applikationerne i vores mobiltelefoner.
- Spørgsmålet om P versus NP fik navn under den kolde krig i 1970'erne og forbindes med forskerne Steve Cook fra USA, og Leonid Levin fra Sovjet. Spørgsmålet har vist sig at være vigtigt, fordi det handler om at forstå forbindelsen mellem mange praktiske problemer. I vores artikel undersøger vi den algebraiske del af problemet. Vi beskriver, hvor svært det er at beregne bestemte polynomier (matematiske funktioner) og viser, at nogle typer polynomier ikke kan beregnes effektivt ved hjælp af bestemte algoritmer, siger Nutan Limaye.
De tre forfattere begyndte at arbejde på forskningsartiklen i 2019, da de arbejdede med relaterede udfordringer. På det tidspunkt arbejdede Nutan Limaye på Indian Institute of Technology Bombay, og faktisk startede hun først i sin stilling som lektor ved IT-Universitetet i september 2021.
Første gang på dansk universitet
Prisen for bedste forskningsartikel har gjort indtryk på hendes nye kollegaer på IT-Universitetet. Leder for Institut for Datalogi, professor Peter Sesoft, bemærker, at det er første gang, at prisen går til forskere på et dansk universitet:
- Dette er enestående og meget prestigefyldt. Inden for algoritmer, er FOCS en af de to mest betydningsfulde konferencer i verden. Bare at det at udgive en forskningsartikel der er en elite-præstation; så meget desto mere betyder det at modtage en Best Paper Award, siger han.
Forskningsartiklen fik også øjeblikkelig anerkendelse af nogle af verdens førende forskere i teoretisk datalogi. Allerede dagen efter offentliggørelsen, tweetede Rahul Santhanam fra Oxford University: ”Årets indtil videre bedste artikel om kompleksitet”, og Thatchapol Saranurak, University of Michigan kaldte det ”Et stort gennembrud”. Nutan Limayes kollega, professor Thore Husfeldt, er ikke overrasket over opmærksomheden:
- Det er hårdt og langsommeligt at arbejde med fremskridt i beregningskompleksitet, selvom området tiltrækker nogle af de bedste hjerner, siger han og forsætter: - så når der endelig kommer et godt resultat, giver det genklang i hele forskningsfeltet. Dette er virkelig en imponerende præstation af Nutan og hendes medforfattere. For en gangs skyld giver det mening at bruge superlativer som “verdensklasse” og “banebrydende.”