13 listopada 2026 15:42
Praca licencjacka naszego studenta na jednej z najważniejszych konferencji informatycznych na świecie!
W dniach 8-11 listopada w Nowym Jorku odbyła się konferencja FOCS - IEEE Symposium on Foundations of Computer Science. FOCS, obok STOC - ACM Symposium on Theory of Computing - to jedna z dwóch najważniejszych konferencji na świecie poświęconych informatyce teoretycznej.
Wśród zaakceptowanych prac znalazły się aż trzy, których współautorami są naukowcy związani z naszym Instytutem:
- Better Bounds For Graph Reconstruction (Antoni Buraczewski i Paweł Gawrychowski). Praca przedstawia nowy algorytm odtwarzania nieznanego grafu rzadkiego, który znacząco zmniejsza liczbę zapytań o odległości między jego wierzchołkami. Praca powstała na podstawie pracy licencjackiej Antoniego Buraczewskiego.
- Dynamic Time Warping in the Low-Distance Regime (Itai Boneh i współautorzy). DTW to popularna miara podobieństwa ciągów. Autorzy pokazują, że przy założeniu odpowiedniej hipotezy złożoności obliczeniowej nie da się szybko obliczyć tej miary nawet dla bardzo podobnych ciągów. Odróżnia to DTW od innych klasycznych miar podobieństwa, dla których takie przyspieszenie jest możliwe.
- k-Clustering via Iterative Randomized Rounding (Jarek Byrka i współautorzy). Praca przedstawia nowy algorytm dla problemów klasteryzacji, osiągający najlepsze znane gwarancje aproksymacji dla kilku klasycznych wariantów tego problemu.
To nie jedyny sukces naszych naukowców na tych konferencjach. Na tegorocznym STOC ukazała się praca Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection, której współautorem jest Bartłomiej Dudek. Dotyczy ona efektywnego sprawdzania, czy dwie dowolne operacje algebraiczne spełniają prawo rozdzielności.
Gratulacje!
(Nowy Jork, fot. Wikimedia Commons)
