Väitös, tietojenkäsittelytiede, DI Minoo Zarsav

Väitöskirjan nimi: Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry

Väittelijä: Minoo Zarsav
Vastaväittäjä: apulaisprofessori Erik Jan van Leeuwen, Utrecht University, Alankomaat 
Kustos: professori Lauri Savioja, Aalto-yliopiston perustieteiden korkeakoulu 

Väitöstilaisuus tietojenkäsittelytieteessä: Minoo Zarsav 

DI Minoo Zarsav väittelee tohtoriksi 25. toukokuuta 2026 klo 12 luentosalissa M1 (M232), Kandidaattikeskus, Otakaari 1, Espoo. 

Väitöskirjan nimi on 
Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry. 

Väitöskirja kuuluu teoreettisen tietojenkäsittelytieteen alaan, erityisesti kombinatoriikan, graafiteorian ja algoritmien tutkimukseen. Työssä esitetään uusia rakenteellisia ja ekstremaalisia tuloksia geometrisista esityksistä syntyville kaksiosaisille graafeille sekä kehitetään algoritmisia viitekehyksiä klassisiin vaikeisiin ongelmiin, kuten maksimaalisen tasapainoisen biklikin ongelmaan. Tulokset osoittavat, kuinka geometriset rajoitteet tuottavat rakenteellista harvuutta ja mahdollistavat paremmat approksimaatiotakuut. 

Vastaväittäjänä toimii apulaisprofessori Erik Jan van Leeuwen (Utrechtin yliopisto) ja kustoksena professori Lauri Savioja (Aalto-yliopisto). Väitöskirja on julkisesti saatavilla Aalto-yliopiston julkaisupalvelussa.

Avainsanat: kaksiosaiset graafit, Ferrers-dimensio, geometriset leikkausgraafit, Zarankiewiczin ongelma, biklikit (bicliques), approksimaatioalgoritmit

Linkki väitöskirjan sähköiseen esittelykappaleeseen (esillä 7 päivää ennen väitöstä): Aalto-yliopiston riiputussivu.