Złożoność drobnoziarnista (fine-grained complexity) jest aktualnie jednym z najbardziej dynamicznie rozwijających się kierunków algorytmiki. Prace poświęcone tej tematyce regularnie pojawiają się na topowych konferencjach typu STOC/FOCS/SODA/ICALP, a poświęcone jej wykłady są prowadzone na najlepszych uczelniach zarówno w Europie (ETH, Saarbruecken), jak i w USA (MIT, Stanford, Harvard). Celem tych zajęć będzie wprowadzenie i przedstawienie najciekawszych (w naszej ocenie) wyników w tej dziedzinie.
Celem fine-grained complexity jest klasyfikacja problemów rozwiązywalnych w czasie wielomianowym. Przykładowo, w problemie APSP chcemy znaleźć odległość między każdą parą wierzchołków w danym ważonym grafie skierowanym. Nie jest trudno rozwiązać ten problem w czasie O(n^3), co być może zaskakujące nie znamy istotnie szybszego algorytmu. Ale jednocześnie nie potrafimy udowodnić, że takiego nie ma! Naturalne jest więc rozważanie całej klasy problemów, które są równoważne APSP (w odpowiednio zdefiniowanym sensie): rozwiązanie dowolnego z nich w czasie O(n^{3-eps}) sprawi, że uzyskamy istotnie szybsze rozwiązanie dla wszystkich innych.
Seminarium będzie złożone z dwóch części. Podczas pierwszej z nich (prowadzonej online) zapoznamy się z podstawowymi technikami używanymi w tej dziedzinie, na podstawie materiałów z wykładów prowadzonych na innych uczelniach, a później (już w formie stacjonarnej) zajmiemy się czytaniem i omawianiem aktualnych prac.
Wśród technik omawianych na pierwszej części znajdzie się sporo takich, które powinny być przystępne już dla studentów, którzy zaliczyli zajęcia z Matematyki Dyskretnej (a z całą pewnością dla tych, którzy zaliczyli Algorytmy i Struktury Danych). W pracach przedstawianych na drugiej części pojawią się pomysły nieco trudniejsze, których zrozumienie może być dobrym wstępem do ambitnej pracy magisterskiej.
