Väitös tietotekniikan alalta, M.Sc. Sorrachai Yingchareonthawornchai

Väitöskirjan nimi: Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization

Tohtoriopiskelija: Sorrachai Yingchareonthawornchai
Vastaväittäjä: Prof. Robert Krauthgamer, The Weizmann Institute of Science, Israel
Kustos: Assist.Prof. Parinya Chalermsook, Aalto-yliopiston perustieteiden korkeakoulu, tietotekniikan laitos

Paikallisesta laskemisesta ja nopeista algoritmeista solmukytkeytyvyyttä varten 

Tämä väitöskirja käsittelee algoritmien kehittämistä verkoston solmukytkeytyvyyden laskemista varten. Sen pääasiallinen tulos on erittäin nopea solmukytkeytyvyysalgoritmi. Solmukytkeytyvyys on eräs tietojenkäsittelytieteen vanhimmista ongelmista, jota on tutkittu 1960-luvulta lähtien. Solmukytkeytyvyys mittaa verkoston kykyä sietää viallisia tai puuttuvia solmuja. Esimerkiksi, matala solmukytkeytyvyys pilviverkostossa mahdollistaa verkoston häiritsemisen tai yhteyden katkaisemisen eliminoimalla pienen määrän verkkolaitteita. Tieteellinen yhteisö on tutkinut solmukytkeytyvyyttä aktiivisesti vuosikymmenten ajan avoimena ongelmana. Suuren verkoston solmukytkeytyvyyden laskeminen kestää hyvin kauan nopeimmilla tätä väitöskirjaa edeltävillä algoritmeilla. Tässä väitöskirjassa palaamme ongelman pariin paikallisen laskemisen näkökulmasta. Paikallisessa laskemisessa tutkitaan mitä voidaan laskea hyödyntämällä pientä osaa syötteestä. Kehitämme sarjan algoritmeja, jotka toimivat tehokkaasti kun solmukytkeytyvyys on matala tai korkea ja lopulta algoritmin, joka laskee solmukytkeytyvyyden “melkein lineaarisessa ajassa”. Melkein lineaarinen aika tarkoittaa, että algoritmin ajoaika kasvaa suurin piirtein suhteessa syötteen lukemista varten vaadittavaan aikaan. Tämä ajoaika on käytännössä paras mahdollinen. Täten, tämä väitöskirja saattaa solmukytkeytyvyyden pitkäaikaisen avoimen ongelman päätökseen.

Linkki väitöskirjan sähköiseen esittelykappaleeseen (esillä 10 päivää ennen väitöstä): https://aaltodoc.aalto.fi/doc_public/eonly/riiputus/

Perustieteiden korkeakoulun väitöskirjat: https://aaltodoc.aalto.fi/handle/123456789/52