Mathias Bæk Tejs Knudsen i toppen af algoritmeforskningen – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Datalogisk Institut, DIKU > Nyheder > DIKU-nyheder 2017 > Mathias Bæk Tejs Knuds...

26. juni 2017

Mathias Bæk Tejs Knudsen i toppen af algoritmeforskningen

Algoritmeforskning

Den 9. juni 2017 gav Mathias Bæk Tejs Knudsen, ph.d.-studerende ved DIKU, en talk ved konferencen Highlights of Algorithms (HALG) på baggrund af en artikel om fundamentale hash funktioner. Talerne ved konferencen består af de ca. 20 forskere, der har præsenteret de mest spændende resultater i algoritmik inden for det sidste år.

Det var artiklen Linear Hashing is Awesome, som blev præsenteret ved konferencen Foundations of Computer Science (FOCS 2016), der bragte Mathias Bæk Tejs Knudsen i det fine selskab til HALG, hvor en stor del af talerne kom fra store amerikanske universiteter som MIT, Stanford, Princeton, Berkeley etc. - og kun tre andre europæiske universiteter var repræsenteret blandt de inviterede talere.

Det er anden gang af HALG afholdes. Ved sidste års konference var DIKU også repræsenteret med professor Stephen Alstrup og professor Mikkel Thorup.

Her giver Mathias Bæk Tejs Knudsen en talk ved ACM Symposium on the Theory of Computing (STOC) den 19. juni 2017.

Linear Hashing is Awesome

Hash funktioner er et fundamentalt redskab i datalogi til at generere systematisk tilfældighed. Denne systematiske tilfældighed bruges overalt i datalogien til at lave hurtigere og mere effektive algoritmer, der bruges som byggesten overalt i fx computere, tablets, telefoner, hjemmesider, routere, etc. Der findes nærmest ikke noget elektronik, hvor det ikke bruges. Et helt fundamentalt problem i denne sammenhæng er repræsentationen af en mængde af objekter, hvor nye elementer kan fjernes, tilføjes og ændres - hvor det hele tiden er vigtigt, at det går så hurtigt og effektivt som muligt. Hvordan den systematiske tilfældighed fungerer kan være svært at analysere og forstå, men er ekstremt vigtigt. Det har både indflydelse på, hvor godt computeren præsterer, og der findes eksempler på, hvordan denne manglende forståelse af den brugte hash-funktion har gjort hackerangreb som "Denial of Service attacks" muligt.

- I min artikel analyserer jeg en af de mest basale hash funktioner, og giver nye resultater om strukturen af den, der viser, at den virker bedre end de fleste forskere troede, når den skal bruges til at repræsentere mængder af objekter. Udover at være basal er den også meget brugt i praksis. Resultatet viser, at den forståelse, vi har haft af hash-funktionen siden 70'erne, ikke er tilstrækkelig, og at den faktisk har nogen egenskaber, som vi ikke har været opmærksomme på de sidste 40 år, fortæller Mathias Bæk Tejs Knudsen.

Læs artiklen her