Algorytmika

czwartek, 14:15 - 16:00, sala 0174

Seminarium o algorytmach i złożoności obliczeniowej, ze szczególnym
uwzględnieniem klasycznych wielomianowych algorytmów i analizy
ograniczeń złożonościowych.

Poprzednie referaty

13.12.2018 14:00
Łukasz Miśkiewicz, Adam Pardyl
Space-Efficient Algorithms for Longest Increasing Subseqence
Najdłuższy rosnący podciąg jest znanym problemem, który można rozwiązać w złożoności O(n*log(n)) używając O(n*log(n)) dodatkowych bitów.
Autorzy pracy prezentują algorytmy korzystające z mniejszej ilości dodatkowej pamięci. Konkretniej, dla sqrt(n) <= s <= n, pokazują sposób obliczania długości najdłuższego rosnącego podciągu w O(1/s * n2 * log(n)) korzystając z O(s * log(n)) dodatkowych bitów oraz obliczanie tego podciągu w czasie O(1/s * n2 * log2(n)) używając tyle samo dodatkowych bitów.
Dodatkowo autorzy dowodzą, że dla danej złożoności pamięciowej złożoności czasowe w modelu dostępu sekwencyjnego są optymalne z dokładnością do czynników polilogarytmicznych.
29.11.2018 14:00
Konrad Deka, Szymon Kapała
Tighter Connections Between Formula-SAT and Shaving Logs
W 2015, Abboud, Backurs i Vassilevska-Williams pokazali że algorytm dla LCS działający w czasie O(n2-eps) implikowałby szybki  algorytm dla CNF-SAT, i tym samym fałszywość SETH. W tej pracy, na podstawie innych hipotez dotyczących SAT, autorzy szukają dolnych ograniczeń postaci O(n2/logc n) dla LCS, a także problemu odległości Frecheta oraz problemu matchowania regexów. Głównym rezultatem jest redukcja z SAT-a na formule wielkości s, mającej n zmiennych, do LCS na ciągach długości 2n/2s1+o(1). Wynika stąd, że algorytm dla LCS działający w O(n2/log7+epsn) implikowałby fałszywość pewnych hipotez o Formula-SAT, a algorytm działający w O(n2/log17+epsn) - znaczący postęp w teorii złożoności obwodów.
22.11.2018 14:00
Rafał Byczek, Bruno Pitrus
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

Odległość edycyjna to jeden ze sposobów zmierzenia jak bardzo dwa ciągi znaków są do siebie podobne. Polega on na zliczeniu minimalnej liczby operacji wstawienia, usunięcia lub zmienienia znaku na inny, wymaganej aby przekształcić jedno słowo w drugie. W tej pracy autorzy skupili się na problemie złożoności obliczeniowej aproksymowania odległości edycyjnej pomiędzy parą słów.

Problem wyznaczenia dokładnej odległości edycyjnej może być rozwiązany za pomocą klasycznego algorytmu dynamicznego działającego w kwadratowym czasie. W 2010 roku Andoni, Krauthgamer i Onak przedstawili działający w czasie prawie liniowym, algorytm aproksymujący odległość edycyjną z polilogarytmicznym czynnikiem aproksymacji. W 2014 Backurs i Indyk pokazali, że dokładny algorytm działający w czasie O(n^(2-δ))implikowałby szybki algorytm dla SAT i fałszywość silnej hipotezy o czasie wykładniczym (SETH). Ponadto, ostatnio w 2017, Abboud i Backurs pokazali, że istnienie algorytmu aproksymującego odległość edycyjną w czasie prawdziwie podkwadratowym z czynnikiem aproksymacji 1 + o(1) implikowałoby fałszywość paru hipotez dotyczących złożoności obwodów boolowskich (circuit complexity). To poddaje w wątpliwość aproksymowalność odległości edycyjnej z dokładnością do czynnika stałego w czasie prawdziwie podkwadratowym.

W tej pracy autorzy jednak odpowiedzieli twierdząco na to pytanie, przedstawiając bardzo ciekawy algorytm aproksymujący odległość edycyjną, z stałym czynnikiem aproksymacji i dowodząc, że jego czas działania jest ograniczony od góry przez Õ(n^(2−2/7)).

15.11.2018 14:00
Tomasz Zieliński, Michał Zwonek
On the Complexity of the (Approximate) Nearest Colored Node Problem
Mając dany graf G = (V, E) gdzie każdy wierzchołek ma przypisany kolor, pytamy o przybliżoną odległość pomiędzy danym wierzchołkiem v a najbliższym jemu kolorowi c. Prezentujemy wyrocznię o rozciągłości 4k-5 wykorzystującą O(kn sigma^(1/k)) przestrzeni i O(log k) czasu zapytania. Następnie dowodzimy, że posiadając estymatę rzędu O(polylog(n)) jesteśmy w stanie w czasie O(1) udzielić odpowiedzi na pytanie o dokładną odległość dist(v, c). Na końcu pokazujemy związek pomiędzy problemem lambda-OuMv a odległością dist(v, c).
08.11.2018 14:00
Weronika Grzybowska, Paweł Mader
Hamming distance completeness and sparse matrix multiplication
Autorzy prezentują polilogarytmiczne redukcje pomiędzy obliczaniem odległości Hamminga a iloczynem skalarnym, w którym miejsce mnożenia zajmuje pewna funkcja binarna na liczbach całkowitych. Dla takich funkcji binarnych należą dominance product, threshold product i odległości l_{2p+1} dla stałego p. Wykorzystując wyżej opisane redukcje, autorzy wykazują równość (z dokładnością do czynników polilogarytmicznych) złożoności wyliczania  powyższych funkcji dla dwóch zbiorów wektorów. Dodatkowo, autorzy dowodzą, że APHam (oraz ten sam problem z użyciem innych wymienionych funkcji) mieści się w czasie polilogarytmicznym od mnożenia macierzy rozmiaru n na nd i nd na n, zawierających po nd niezerowych wartości.
25.10.2018 14:00
Filip Bartodziej, Vladyslav Hlembotskyi
Fine-grained Lower Bounds on Cops and Robbers
Sumienni policjanci, czy sprytny złodziej? Na tym seminarium dowiemy się kto triumfuje, jak szybko (lub jak wolno) jesteśmy w stanie się o tym przekonać i ilu policjantów wystarczy, aby przyskrzynić nawet samego Frank’a Abagnale’a. Rozważania bedą oparte o grę strategiczna w policjantów i złodziei na grafie (cops and robbers). Uzyskane wyniki opierają sie na założeniu SETH/ETH.
18.10.2018 14:00
Jan Mełech, Rafał Burczyński
A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum
Celem znanego problemu NP-zupełnego Subset-Sum jest znalezienie takiego
podzbioru multizbioru o mocy n, którego suma elementów wynosi t. Autorzy
prezentują krótkie probabilistyczne rozwiązanie bazujące na szybkiej
transformacie Fouriera oraz manipulacjach na funkcjach tworzących działające
w czasie O((n+t)*polylog(t)) i zwracające odpowiedź z prawdopodobieństwem
błędu rzędu O(1/(n+t)). Ten wynik został osiągnięty wcześniej, jednak praca
upraszcza rozwiązanie, zawierając je raptem w kilku stronach.
11.10.2018 14:00
Dawid Pyczek, Michał Zieliński
On the Worst-Case Complexity of TimSort
TimSort jest bardzo interesującym algorytmem sortującym, który został wprowadzony do Pythona stosunkowo niedawno, bo w 2002 roku. Ten bardzo popularny algorytm używany jest z powodzeniem na całym świecie. Wynika to z faktu, że działa on wyjątkowo szybko na częściowo posortowanych danych. Aż do niniejszej pracy nie była znana pesymistyczna złożoność tego algorytmu -- w pracy pokazane zostanie, że pesymistyczna złożoność algorytmu TimSort wynosi O(n log n). Następnie złożoność algorytmu ograniczymy przez O(n+n log ρ), gdzie ρ to ilość przebiegów. Pierwsza złożoność w bezpośredni sposob wynika z drugiej, ale oba dowody są ciekawe i pomagają lepiej zrozumieć działanie TimSorta.
Dodatkowo w wyniku analizy algorytmu autorzy pracy odryli błąd w implementacji TimSorta w Javie.
16.03.2017 14:15
Jakub Cisło, Grzegorz Jurdziński
Tight Hardness Results for LCS and other Sequence Similarity Measures
09.03.2017 14:00
Sylwester Klocek, Wojciech Kruk
The Alternating Stock Size Problem and the Gasoline Puzzle
05.01.2017 14:15
Jan Derbisz, Jakub Łabaj
Sortowanie przez spacer po drzewie

Rozważamy następujący problem: wierzchołki drzewa ponumerowane są kolejnymi liczbami naturalnymi, a dodatkowo w wierzchołku x leży skrzynka o numerze p(x), przy czym funkcja p jest permutacją zbioru {1,2,..,n}. Rozważamy chodzącego po drzewie robota, który może w danym momencie trzymać tylko jedną skrzynkę, może też podnieść napotkaną skrzynkę upuszczając aktualnie trzymaną. Celem robota jest posortować skrzynki (przenosząc każdą do wierzchołka o odpowiednim numerze), przechodząc po drzewie najkrótszą możliwą ścieżką. Praca D. Grafa podaje algorytm znajdujący taką ścieżkę w czasie O(n2) oraz dowód, że jeśli drzewo zastąpimy grafem planarnym, problem staje się NP-zupełny.

15.12.2016 14:15
Michał Glapa, Franciszek Stokowacki
Skojarzenia w grafach metodami algebraicznymi
Na seminarium omówiony zostanie przełomowa praca z 2006, autorstwa Muchy i Sankowskiego, opisująca algorytm obliczania skojarzeń w grafach za pomocą eliminacji Gaussa. Przedstawiony algorytm ma złożoność zależną od mnożenia macierzy, niższą niż O(n2.5), algorytmu Micaliego-Vaziraniego, który bardzo długo był najlepszą znaną metodą.
08.12.2016
Lech Duraj
Krótka opowieść o mnożeniu macierzy

W ostatnich latach pojawiają się kolejne, coraz lepsze algorytmy mnożenia macierzy. Każdy z nich jest jednak tylko nieznacznie szybszy od poprzednich, będąc przy tym nierównie trudniejszy w zrozumieniu i analizie. Fakt ten jeszcze bardziej komplikuje otwarte od wielu lat pytanie o złożoność optymalnego algorytmu mnożenia macierzy.

Celem prezentacji jest krótkie omówienie technik używanych do ataków na ten niezwykle ważny i trudny problem. Prezentacja oparta jest na przeglądowym wykładzie François Le Galla (autora ostatnich wyników w tym temacie) z 2014 roku.

01.12.2016
Aleksandra Mędrek, Krzysztof Maziarz
Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Praca Aleksandra Mądrego opisuje nowe podejście do problemu maksymalnego przepływu, z użyciem tzw. przepływów elektrycznych. W tej technice krawędziom przypisywany jest opór, a zadaniem jest zminimalizowanie wydzielonej energii. Dowolną sieć przepływową można zredukować do zadania przepływu elektrycznego, z użyciem pośredniej redukcji poprzez warianty problemu skojarzenia w grafie dwudzielnym. Głównym rezultatem pracy jest algorytm przepływu o złożoności O(m10/7), na seminarium będzie prezentowana prostsza wersja algorytmu, działająca w O(m3/2).

24.11.2016
Dominika Salawa, Jakub Cisło
Greedy algorithms for Steiner forest

Referowana praca rozstrzyga długo otwarty problem: czy budowanie drzewa Steinera zachłannym algorytmem daje wynik gorszy od optymalnego o stałą multiplikatywną? Autorzy (A. Gupta, A. Kumar) dowodzą, że tak, dla stałej równej 96. Jest to pierwsze znane oszacowanie wyniku algorytmu zachłannego, wcześniej podawane algorytmy aproksymacyjne dla tego problemu oparte były o programowanie liniowe.

17.11.2016
Patryk Gołębiowski, Wojciech Kruk
Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms
Tematem referatu jest praca Colina White'a dotycząca algorytmów poszukiwania ścieżki na grafach o szczególnym własnościach, mających w założeniu modelować rzeczywiste sieci dróg. Autor analizuje najpopularniejsze istniejące algorytmy i podaje dolne ograniczenia na ich złożoność.
10.11.2016
Magdalena Gargas, Mateusz Jachna
Max flows in O(nm) time, or better
W pracy opisany jest nowy algorytm przepływu działający w czasie O(nm + m16/15 logn). Istotny jest fakt, że przez połączenie go z poprzednio znanymi algorytmami daje to pozytywną odpowiedź na pytanie, czy da się obliczyć maksymalny przepływ w czasie O(nm). Autorem pracy jest James B. Orlin.
03.11.2016
Krzysztof Francuz, Szymon Łukasz
Fast and simple connectivity in graph timelines

Referowana praca (autorstwa J. Łąckiego i A. Karczmarza) rozważa grafy, w którym krawędzie podlegają zmianom - są dodawane bądź usuwane. Opisany jest efektywny algorytm odpowiadający na pytania o osiągalność (istnienie ścieżki między dwoma wierzchołkami) i dwuspójność (istnienie dwóch rozłącznych ścieżek) na zadanych przedziałach czasowych.

27.10.2016
Dawid Pyczek, Jakub Rówiński
Faster deterministic sorting and priority queues in linear space

Dolne ograniczenie O(n log n) na problem sortowania obowiązuje tylko, jeśli na sortowanych obiektach nie można wykonać żadnych operacji innych niż porównanie. Jeżeli natomiast sortujemy liczby całkowite, możliwe są szybsze algorytmy - referowana praca Mikkela Thorupa z 1997 opisuje algorytm działający w O (n (log log n)2).

20.10.2016
Mateusz Twaróg, Patryk Urbański
Disjoint Set Union with randomized linking

Algorytm Find-Union w najbardziej znanej wersji implementowany jest przez las zbiorów rozłącznych z kompresją ścieżek i łączeniem według rang. Prezentowana praca, autorstwa Goela, Khanny, Larkina i Tarjana, analizuje złożoność w wersji z arbitralnym (losowym) łączeniem drzew.

13.10.2016
Grzegorz Bukowiec, Sylwester Klocek
Algorytm FKT
Rozstrzygnięcie, czy w grafie istnieje skojarzenie, oraz znalezienie takiego skojarzenia są problemami łatwymi obliczeniowo. Liczenie wszystkich skojarzeń jest jednak problemem #P-zupełnym - wielomianowy algorytm na ten problem pociągałby równość P = NP. Istnieje jednak sposób na policzenie skojarzeń dla pewnej klasy grafów - w szczególności, dla wszystkich grafów planarnych. Algorytm taki - zwany od nazwisk twórców algorytmem FKT - wykorzystuje bliski związek między pojęciami (łatwego obliczeniowo) wyznacznika i (trudnego) permanentu macierzy.
16.03.2016 14:15
Jakub Cisło, Grzegorz Jurdziński
Tight Hardness Results for LCS and other Sequence Similarity Measures