Smartere algoritmer for store skjulte data

Mange beregningsproblemer blir vanskelige fordi antallet mulige løsninger er enormt. I stedet for å skrive ut alle løsningene én etter én, kan man ofte beskrive dem mer kompakt ved hjelp av symbolske datastrukturer. Avhandlingen til Wim Van den Broeck undersøker hvordan slike kompakte beskrivelser kan brukes til å lage raskere algoritmer, og hvor grensene for slike metoder går.

Arbeidet viser hvordan ideer fra parameterisert kompleksitet kan brukes til å forstå symbolske algoritmer på en mer systematisk måte. Et hovedpoeng er at det ikke bare er størrelsen på det opprinnelige problemet som betyr noe, men også hvor enkelt problemet kan beskrives symbolsk.

Avhandlingen studerer blant annet forbindelsen mellom dynamisk programmering og lineær programmering, og viser hvordan gode dynamisk-programmeringsalgoritmer kan gi gode lineære formuleringer. Den undersøker også hvordan kompakte representasjoner av boolske funksjoner kan deles opp i enklere deler, noe som kan gjøre dem lettere å lagre, analysere og bruke.

I den siste delen ser avhandlingen på databaseforespørsler. Her handler det om å finne gode måter å utføre store sammenslåinger av tabeller på, slik at man unngår unødvendig store mellomresultater. Resultatene kan bidra til en bedre teoretisk forståelse av hvordan slike spørringer bør optimaliseres.

Samlet viser avhandlingen at symbolske representasjoner kan være et kraftig verktøy for å håndtere store beregningsproblemer, men også at det kreves en presis forståelse av når slike representasjoner faktisk gir effektive algoritmer.

Personalia

Wim Van den Broeck begynte på bachelorprogrammet i nanoteknologi ved Universitetet i Bergen, men byttet senere til informatikk. Han tok deretter mastergrad i logikk ved UiB, med Michał Walicki som veileder. I 2022 startet han på doktorgraden i informatikk under veiledning av Mateus de Oliveira Oliveira. Han er nå forsker ved TU Ilmenau i Tyskland.