Algorytmika

dr Lech Duraj

środa 14:15 - 16:00, sala 1103

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

26.10.2023 14:15
Jan Klimczak, Szymon Wojtulewicz
Approximating Knapsack and Partition via Dense Subset Sums
Kwestia złożoności (1 - ε)-aproksymacji problemu plecakowego i problemu podziału pozostaje nierozstrzygnięta. Prezentujemy algorytmy:  
- (1 - ε)-aproksymacja problemu plecakowego w złożoności O(n + (1/ε)^(2.2))  
- (1 - ε)-aproksymacja problemu podziału w złożoności O(n + (1/ε)^(1.25))
Obie techniki wykorzystują poprzednie rezultaty na temat konwolucji gęstych zbiorów. Wykorzystane zostały też nowe sposoby przyspieszenia metody 'dziel i zwyciężaj', która jest często wykorzystywana w problemach addytywnych.
12.10.2023 14:15
Kacper Topolski, Jakub Wąs
Simple and Faster Algorithms for Knapsack
Na tym seminarium zdefiniujemy problem plecakowy oraz jego wariacje - wersję 0-1, ograniczoną oraz DiffKnapsack. Przybliżymy najnowsze rezultaty związane z tym problemem. W szczególności zaprezentujemy prosty algorytm randomizowany rozwiązujący dyskretny wariant problemu plecakowego oraz oparty na nim algorytm rozwiązujący wersję ograniczoną. Jest on rozwinięciem pierwszego algorytmu o liniowej zależności względem liczby elementów, zaprezentowanego m.in. przez Adama Polaka.
12.10.2023 14:15
Kacper Topolski, Jakub Wąs
Simple and Faster Algorithms for Knapsack
Na tym seminarium zdefiniujemy problem plecakowy oraz jego wariacje - wersję 0-1, ograniczoną oraz DiffKnapsack. Przybliżymy najnowsze rezultaty związane z tym problemem. W szczególności zaprezentujemy prosty algorytm randomizowany rozwiązujący dyskretny wariant problemu plecakowego oraz oparty na nim algorytm rozwiązujący wersję ograniczoną. Jest on rozwinięciem pierwszego algorytmu o liniowej zależności względem liczby elementów, zaprezentowanego m.in. przez Adama Polaka.
27.04.2023 14:15
Justyna Jaworska, Jakub Siuta
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance
Dla problemów znjadowania odległości edycyjnej i odległości edycyjnej Dycka chcemy znaleść szybkie, deterministyczne i proste aproksymacje, z być może dużym współczynnikiem aproksymacji. Dla klasycznej odległości edycyjnej wprowadzimy klasę szybkich i prostych algorytmów nazywanych "algorytmami pojdedycznego skanowania". Saha, w 2014. roku, podał randomizowany algorytm z tej klasy osiągający aproksymację O(d) dla słow x, y takich że ich ogległość edycyjna jest rzędu O(d). W tej pracy prezentujemy: (1) deterministyczny algorytm z wymienionej klasy osiągający podobne rezultaty oraz (2) dowodzimy, że nie istnieje (nawet randomizowany) algorytm z tej klasy, który dawałby lepszą aproksymację. Dla odległości edycyjnej Dycka, Saha zaproponował randomizowaną redukcję z odległości edycyjnej Dycka do klasycznej odległości edycyjnej o koszcie O(log d), gdzie d to odległość edycyjna Dycka. Podamy redukcję deterministyczną której zarówno sfromułowanie jak i udowodnienie poprawności jest prostsze.
13.04.2023 14:15
Rafał Pyzik, Sebastian Spyrzewski
Treewidth is NP-Complete on Cubic Graphs (and related results)
Autorzy pracy podają prosty dowód NP-zupełności problemu Treewidth, udowadniając jego NP-zupełność w klasie dopełnień grafów dwudzielnych. Praca poprawia też rezultat Bodlaedera i Thilikosa z roku 1997 mówiący, że Treewidth jest NP-zupełne w grafach o maksymalnym stopniu co najwyżej 9, pokazując NP-zupełność w grafach regularnych stopniu 3.
30.03.2023 14:15
Łukasz Grobelczyk, Rafał Loska
This Game is Not Going to Analyze Itself
Praca analizuje kilka problemów powiązanych z grą przeglądarkową "This Game Is Not Going To Load Itself", w której gracz ma za zadanie przekierować poruszające się kolorowe kwadraty do odpowiedniego ujścia na planszy poprzez ustawianie na niej kolorowych strzałek. Problem decyzyjny czy można wygrać grę jest w klasie $\Sigma_2^P$, jest NP-trudny w wersji offline, a nawet bez możliwości układania strzałek przez gracza jest zarówno NP- jak i coNP-trudny. Praca analizuje również problem istnienia strategii wygrywającej.
26.01.2023 14:15
Grzegorz Gawryał, Szymon Salabura
TSP in a Simple Polygon
Problem komiwojażera (TSP) jest jednym z najbardziej popularnych problemów optymalizacyjnych w algorytmice. Jest on NP-trudny, nawet wtedy, gdy graf na wejściu jest grafem odległości euklidesowych między danymi punktami na płaszczyźnie. Autorzy wprowadzają nowy wariant tego problemu - TSP w wielokącie prostym, w którym to problemie należy znaleźć najkrótszą trasę nie wychodzącą poza wielokąt i odwiedzającą pewien zbiór punktów w tym wielokącie, w dowolnej kolejności. Autorzy najpierw pokazują, jak zastosować ogólniejszy i dość skomplikowany algorytm Marxa, Pilipczuka i Pilipczuka do tego problemu, uzyskując złożoność poly(n,m) + 2(O(sqrt(n) log n)), a następnie prezentują własny, znacznie prostszy algorytm rozwiązujący ten wariant TSP w tej samej złożoności.
19.01.2023 14:15
Bartłomiej Wacławik, Krzysztof Ziobro
Tiny Pointers
Praca wprowadza nowe pojęcie: wskaźniczek. Wskaźniczek jest obiektem, który pozwala na 
dostęp do jednego z n miejsc w pamięci, jednocześnie używając znacząco mniej niż log(n)
bitów. Jest to możliwe dzięki użyciu wprowadzonej w pracy tablicy dereferencyjnej, która
pozwala dla danego klucza k (z dużym prawdopodobieństwem) zaalokować komórkę pamięci
zwracając wskaźniczek, który razem z kluczem pozwalaja uzyskać dostęp do zaalokowanej
komórki w czasie stałym. Dodatkowo autorzy podają przykłady zastosowań w popularnych
strukturach danych, których rozmiar można zredukować dzięki zastąpieniu klasycznych 
wskaźników wskaźniczkami. Wśród tych przykładów znajdują się między innymi drzewa BST
oraz słowniki o stałej pojemności. 
12.01.2023 14:15
Ignacy Buczek, Tomasz Buczyński
List Colouring Trees in Logarithmic Space
Dla danego n-wierzchołkowego grafu G = (V, E) oraz listy L(v) ⊆ {1, ..., n} dozwolonych kolorów dla każdego wierzchołka v ∊ V, kolorowanie listowe jest kolorowaniem wierzchołkowym c grafu G spełniającym c(v) ∊ L(v) dla każdego v. Autorzy pracy dowodzą, że problem kolorowania listowego n-wierzchołkowych drzew może być rozwiązany za pomocą deterministycznej maszyny Turinga używającej O(log n) bitów na taśmie roboczej.
22.12.2022 14:15
Kamil Galewski, Piotr Kaliciak
Lower Bounds on Retroactive Data Structures
15.12.2022 14:15
Roman Madej, Paweł Nowak
Sinkless Orientation Made Simple
Sinkless Orientation jest problemem grafowym, polegającym na skierowaniu krawędzi w grafie, aby każdy wierzchołek o stopniu co najmniej trzy miał krawędź wychodzącą. Problem ten odgrywa kluczową rolę w zrozumieniu teorii obliczeń rozproszonych.
Tematem rozważań pracy będzie analiza lokalności problemu, jednej z podstawowej własności rozproszonych algorytmów grafowych, w modelach LOCAL i SLOCAL. Znane jest już dokładne ograniczanie w modelu LOCAL oraz ograniczenie górne w modelu SLOCAL, natomiast standardowe dowody wykorzystują zaawansowane techniki. W pracy autorzy prezentują jednak nowe, elementarne i samowystarczalne dowody obydwu ograniczeń.
01.12.2022 14:15
Tomasz Mazur, Katzper Michno
Constrained Backward Time Travel Planning is in P
Tematem rozważań będą sieci transportowe modelowane przez dynamiczne grafy, w których wierzchołkach dopuszczalne jest cofanie się w czasie, przy czym nie można cofnąć się o więcej niż pewną liczbę jednostek oraz jest ono obarczone kosztem wyrażonym pewną funkcją kosztu. Skupiamy się na dynamicznych grafach będącymi podgrafami ścieżki. W szczególności podajemy algorytmy wielomianowe dla różnych wariantów szukania trasy z jednego wierzchołka do drugiego minimalizującej w pierwszej kolejności opóźnienie (różnicę między  czasem dotarcia a wyruszenia), a drugiej sumaryczny koszt cofania się w czasie. Warianty różnią się ograniczeniami na to, jak możemy cofać się w czasie. 
Badamy wpływ wyboru funkcji kosztu cofania na problem obliczania optymalnej trasy oraz podajemy warunki konieczne dla funkcji kosztu, aby optymalna trasa istniała. Na koniec podajemy optymalny algorytm on-line na szukanie optymalnej trasy dla funkcji kosztu będącej identycznością, w przypadku, gdy możemy cofać się dowolnie daleko w czasie.
24.11.2022 14:15
Dominik Chmura, Jan Klimczak
Derandomized Squaring of Graphs

Praca opisuje "zderandomizowany" odpowiednik podnoszenia grafu do kwadratu. Nowa operacja zwiększa spójność grafu (mierzoną jako druga co do wielkości wartość własna macierzy sąsiedztwa) prawie tak dobrze jak potęgowanie grafu, zwiększając stopień grafu nie kwadratowo, a jedynie o stałą. 

Przedstawiono również kilka zastosowań tej konstrukcji, m.in. algorytm alternatywny do wyniku O. Reingolda, który pozwala deterministycznie badać osiągalność w grafach nieskierowanych w logarytmicznej pamięci.

17.11.2022 14:15
Bartłomiej Błoniarz, Hubert Dej
More on Change-Making and Related Problems

Mając do dyspozycji zbiór n typów monet o wartościach całkowitych oraz wartość docelową t, w problemie wydawania reszty (change-making) szukamy minimalnej liczby monet, które sumują się do t, zakładając możliwość wykorzystania dowolnej liczby monet każdego typu.

W bardziej ogólnej wersji tego problemu (w wersji all-targets), chcemy obliczyć wyniki dla wszystkich wartości docelowych 0, 1, ..., t. Klasyczny algorytm dynamiczny rozwiązuje ten problem w czasie O(nt).

W publikacji autorzy przedstawiają szereg nowych wyników dotyczących problemu wydawania reszty i innych pokrewnych problemów. Dla u – wartości największej z monet (wagi najcięższego przedmiotu w przypadku problemu plecakowego) pokażemy algorytmy o złożoności:
- Õ(u2+t) dla all-target change-making w oparciu o twierdzenie Erdősa i Grahama dotyczące problemu Frobeniusa;
- Õ(u2+t) dla all-capacities knapsack w oparciu o wcześniejszy algorytm dla change-making;
- Õ(u) dla single-target change-making w oparciu o FFT;
- Õ(nu) dla single-capacity unbounded knapsack, przez wprowadzenie zachłanności umożliwiającej pominięcie obliczania niektórych podproblemów.

03.11.2022 14:15
Katarzyna Kępińska, Sebastian Spyrzewski
Fully Dynamic Four-Vertex Subgraph Counting
27.10.2022 14:15
Łukasz Selwa, Juliusz Wajgelt
Token sliding on graphs of girth five

Intuicyjnie problem Token Sliding możemy rozumieć jako grę, w której otrzymujemy graf oraz żetony ustawione na jego wierzchołkach. Pytamy, czy da się uzyskać zadany stan końcowy poprzez przesuwanie żetonów wzdłuż krawędzi grafu tak, że w żadnym momencie dwa żetony nie łączyła wspólna krawędź.

Formalnie mamy na wejściu graf G oraz zbiory niezależne wierzchołków Is, It i chcemy stwierdzić czy istnieje sekwencja I1, …, Is zbiorów niezależnych w G taka, że I1 = Is, Il = It oraz Ii ∆ Ii+1 = {u, v} \in E(G).

Wykazano wcześniej, że dla grafów o talii (ang. girth) 4 lub mniejszej problem Token Sliding jest W[1]-trudny. 

Prezentujemy dowód z pracy „Token sliding on graphs of girth five”, że dla grafów o talii 5 lub większej problem Token Sliding  jest fixed-parameter tractable (FPT).

20.10.2022 14:15
Julia Biały, Zofia Glapa
All Paths Lead to Rome

Roma to łamigłówka rozgrywana na składającej się z kwadratowych pól planszy rozmiaru n x n. Pola pogrupowane są w obszary składające się z co najwyżej 4 sąsiadujących ze sobą komórek, z których każda albo jest wypełniona, albo ma zostać wypełniona strzałką w jednym z 4 kierunków. Celem gry jest wypełnienie wszystkich komórek strzałkami tak by w każdym obszarze była co najwyżej jedna strzałka w danym kierunku i by podążając zgodnie ze strzałkami można było dojść do wyróżnionego pola Roma z każdego pola na planszy.

Autorzy pracy rozważają złożoność obliczeniową gry i pokazują, że uzupełnienie planszy zgodnie z zasadami jest problemem NP-zupełnym, zliczenie możliwych rozwiązań jest #P zupełne oraz wyznaczenie liczby zadanych z góry strzałek koniecznych by gra miała tylko jedno rozwiązanie jest ΣP2 - zupełne.

Praca dowodzi też, że zakładając prawdziwość ETH problem uzupełnienia planszy dla danej instancji gry nie może być rozwiązany w czasie O(2o(n)). Omawia także algorytm programowania dynamicznego rozwiązujący planszę gry, opierający się na strukturach Catalana.

02.06.2022 14:15
Jędrzej Kula, Maciej Nemś
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

Grafy przecięć geometrycznych to grafy, gdzie wierzchołki odpowiadają figurom geometrycznym w d-wymiarowej przestrzeni euklidesowej. Mogą do to być na przykład kule, kwadraty, hiperkostki. Krawędź między dwoma wierzchołkami istnieje, jeśli dwie figury przecinają się. Jest to typowy sposób modelowania na przykład komunikacji bezprzewodowej.

W pracy autorzy zajmują się obliczaniem średnicy tego typu grafów. Dokładniej rozważają to, czy da się ten problem rozwiązać w czasie poniżej kwadratowym względem liczby wierzchołków. Na referacie zostanie pokazany dowód algorytmu o czasie działania O(n logn) dla sprawdzania, czy średnica jest mniejsza bądź równa 2 dla grafów przecięć kwadratów jednostkowych równoległych do osi. Następnie zostanie pokazane dolne ograniczenie szukania średnicy dla kul jednostkowych na bazie Orthogonal Vectors Hypothesis. Ograniczenie to pokazuje, że nie ma algorytmów pod kwadratowych przy założeniu Orthogonal Vectors Hypothesis.

26.05.2022 14:15
Grzegorz Gawryał, Rafał Kilar
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
19.05.2022 14:15
Andrii Orap, Maksym Zub
Grundy Distinguishes Treewidth from Pathwidth

Strukturalne parametry grafów, takie jak treewidth, pathwidth i clique-width, są głównym tematem badań sparametryzowanej złożoności. Głównym celem badań w tej dziedzinie jest zrozumienie „ceny ogólności” tych szerokości: kiedy przechodzimy od pojęć bardziej restrykcyjnych do bardziej ogólnych, jakie są problemy, w których złożoność pogarsza się z fixed-parameter tractable do intractable? Ten rodzaj pytania jest już bardzo dobrze zbadany, ale, co jest dość uderzające, algorytmiczna granica między dwoma (prawdopodobnie) najbardziej centralnymi pojęciami szerokości (notacjami), treewidth i pathwidth, jest nadal niezrozumiała: obecnie nie jest znany żaden naturalny problem na grafie, który byłby W-trudny dla jednego, ale FPT dla drugiego. Rzeczywiście, zaskakującym rozwojem ostatnich kilku lat była obserwacja, że: w przypadku wielu najbardziej paradygmatycznych problemów ich złożoność dla tych dwóch parametrów w rzeczywistości dokładnie się pokrywają, pomimo faktu, że szerokość drzewa jest parametrem o wiele bardziej ogólnym. W ten sposób wydaje się, że dodatkowa ogólność szerokości drzewa nad szerokością ścieżki często przychodzi „za darmo”.

Naszym głównym wkładem w ten artykuł jest odkrycie pierwszego naturalnego przykładu, w którym ta ogólność ma wysoką cenę. Rozważamy Grundy Coloring, wariację kolorowania, w której próbujemy obliczyć najgorsze możliwe kolorowanie, które można przypisać do grafu przez zachłanny algorytm First-Fit . Pokazujemy, że ten dobrze zbadany problem jest parametryzowany (FPT) przez pathwidth; jednakże to staje się znacznie trudniejsze (W[1]-hard), gdy jest sparametryzowany przez treewidth. Ponadto pokazujemy, że Grundy Coloring sprawia, że jest drugi skok złożoności dla bardziej ogólnych szerokości, gdy staje się para-NP-hard dla clique-width. Dlatego Grundy Coloring ładnie oddaje złożoność kompromisów między trzema najlepiej zbadanymi parametrami. Uzupełniając obraz, pokazujemy, że Grundy Coloring jest parametryzowane przez FPT według modular-width.

12.05.2022 14:15
Nazarii Denha, Ruslan Yevdokymov
Finding Balance-Fair Short Paths in Graphs
05.05.2022 14:15
Krzysztof Pióro, Krzysztof Potępa
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance

W problemie odległości między drzewami dane są dwa ukorzenione drzewa z etykietami na krawędziach. Dodatkowo dla każdego wierzchołka jego dzieci mają ustalony porządek. Naszym celem jest znalezienie minimalnej liczby operacji kontrakcji krawędzi i zmiany etykiety krawędzi, tak aby doprowadzić oba drzewa do takiego samego drzewa.

Autor pracy pokazuje algorytm o złożoności O(n2.9546) dla wariantu tego problemu, w którym operacje mają koszty jednostkowe. Jest to pierwszy podsześcienny algorytm dla problemu odległości edycyjnej między drzewami. Warto tutaj zwrócić uwagę, że dla wariantu o dowolnych kosztach operacji istnieje warunkowe ograniczenie dolne, które mówi, że nie istnieje dla tego problemu algorytm podsześcienny. Zatem autor pokazuje, że wariant z jednostkowymi kosztami najprawdopodobniej jest istotnie prostszy od wariantu ogólnego.

Aby złamać granicę O(n3) autor redukuje problem do mnożenia macierzy max-plus, w których sąsiednie elementy różnią się co najwyżej o stałą. O takim problemie zostało już udowodnione wcześniej, że może zostać rozwiązany w czasie podsześciennym. 

28.04.2022 14:15
Jakub Fedak, Mateusz Golonka
Wordle is NP-hard
Wordle jest grą dla jednego gracza, której celem jest zgadnięcie pewnego słowa x wybranego ze słownika D. Aby zgadnąć słowo x gracz może wykonać co najwyżej k prób, przy czym w każdej próbie gracz musi podać słowo, które również znajduje się w słowniku D. Wszystkie słowa w słowniku mają długość n. Po każdej próbie zgadnięcia gracz otrzymuje informację o pozycjach, na których jego słowo zgadza się z rozwiązaniem oraz o literach z podanego słowa, które znajdują się w rozwiązaniu, lecz na innej pozycji. Autorzy udowadniają, że następujący problem jest NP-trudny: mając dany słownik D oraz liczbę naturalną k powiedzieć, czy gracz może zagwarantować zgadnięcie słowa w k próbach. Ponadto autorzy dowodzą, że dla słów długości 5 ten problem pozostaje trudny, a nawet w tym przypadku przybliżenie najmniejszej liczby prób potrzebnej do zagwarantowania zgadnięcia słowa jest NP-trudne. W pracy znajdują się również wyniki dotyczące złożoności parametryzowanej oraz kilka pytań otwartych związanych z tym tematem.
21.04.2022 14:15
Piotr Kaliciak, Kamil Galewski
A Simple Algorithm for Graph Reconstruction
Praca skupia się na efektywnej rekonstrukcji grafu, przy pomocy zapytań o odległości między wierzchołkami. Rozważane grafy są spójne, nieważone oraz mają ograniczony stopień, a celem jest znalezienie wszystkich krawędzi w grafie.
Analizowany jest prosty algorytm rekonstrukcji. Autorzy dowodzą, że na ∆-regularnym grafie wykonuje on O(n*polylog(n)) zapytań. Ponadto można go zmodyfikować pod inne rodzaje zapytań. Co więcej, algorytm ten łatwo jest zrównoleglić. W przypadku grafów o ograniczonym stopniu, algorytm potrzebuje o(n2) zapytań.
07.04.2022 14:15
Bartłomiej Błoniarz, Inka Sokołowska
On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
Unbounded SubsetSum to problem w którym dane są liczby c,u oraz n liczb całkowitych w1,...,wn z przedziału [1,u]. Trzeba odpowiedzieć na pytanie czy istnieją liczby całkowite m1,...,mn spełniające c = w1*m1 + ... + wn*mn. W wersji all-target problemu dana jest liczba naturalna t i należy podać odpowiedź dla wszystkich instancji z c z przedziału [0,t].
Praca skupia się na trzech generalizacjach tego problemu:
1. All-target Unbounded Knapsack - wariant dobrze znanego problemu plecakowego, dla którego przedstawiony jest algorytm Õ(T(u)+t) gdzie T(n) to czas obliczania (min,+)-splotu dla tablic długości n
2. All-target CoinChange - wariant problemu wydawania reszty, dla którego przedstawiony jest algorytm Õ(u+t)
3. Residue Table, dla którego przedstawiony jest algorytm Õ(u).
31.03.2022 14:15
Tomasz Buczyński, Łukasz Gniecki
On Determinism Versus Non-Determinism and Related Problems
Pokazujemy, że dla wielotaśmowych maszyn Turinga działających w czasie liniowym, niedeterminizm jest mocniejszy od determinizmu, czyli że klasa języków rozpoznawanych przez takie maszyny deterministyczne jest ścisłą podklasą języków rozpoznawanych przez takie maszyny niedeterministyczne.
24.03.2022 14:15
Mateusz Pach, Michał Wronka
Making Life More Confusing for Firefighters
Problem Firefighter polega na opracowaniu strategii rozsyłania strażaków do obrony wierzchołków grafu przed rozprzestrzeniającym się przez krawędzie ogniem, tak by jak najmniej wierzchołków spłonęło; problem ten jest NP-trudny dla znakomitej większości klas grafów. By zamodelować scenariusz z cywilami pomagającymi strażakom, wprowadzamy problem Temporal Firefighter będący rozszerzeniem na dynamiczne grafy. Pokazujemy, że problem Temporal Firefighter jest NP-trudny i pozostaje taki dla wszystkich klas grafów (poza jedną) o których wiadomo, że posiadają wielomianowe rozwiązanie problemu Firefighter. Pokazujemy też algorytm FPT dla Temporal Firefighter, parametryzowany wartością vertex-interval-membership-width.
17.03.2022 14:15
Ignacy Buczek, Michał Woźny
Sorting Balls and Water: Equivalence and Computational Complexity

Problemy sortowania od długiego czasu są obiektem różnego rodzaju badań. Ostatnio dwie gry na telefon w tematyce sortowania zyskały na popularności. W tych grach, gracz ma do dyspozycji urny wypełnione kolorowymi obiektami (w przypadku jednej są to kule, a w przypadku drugiej woda) oraz kilka pustych urn, a jego celem jest posortowanie obiektów zgodnie z kolorami. W jednym ruchu może on przenieść obiekty z jednej urny do drugiej, jeżeli kolor przenoszonych obiektów zgadza się z kolorem najwyższego obiektu docelowej urny lub urna ta jest pusta.

W pracy autorzy badają złożoność obliczeniową tych łamigłówek. Na początku pokazują, że te gry są w równoważne pod kątem rozwiązywalności. Dokładniej mówiąc, rozwiązywalność stanu początkowego gry nie zależy od tego czy obiekty zachowują się jak kule, czy jak woda. Dowodzą również, że dla każdej tak-instancji istnieje rozwiązanie wielomianowego rozmiaru, co pokazuje, że problem rozwiązywalności tych łamigłówek jest w NP. Następnie uzasadniają, że ten problem jest NP-zupełny. Znajdują również wielomianowe algorytmy dla szczególnych przypadków. Na samym końcu zastanawiają się, jak wiele pustych urn jest potrzebnych, aby instancja była rozwiązywalna niezależnie od początkowego rozmieszczenia obiektów. Pokazują nietrywialne ograniczenia (dolne i górne) zależne od ilości początkowo zapełnionych urn i ich pojemności.

25.11.2021 14:15
Miłosz Januszewski, Szymon Salabura
A Fine-Grained Perspective on Approximating Subset Sum and Partition

W problemie Subset Sum, mając dany zbiór dodatnich liczb X oraz cel t, pytamy czy istnieje dowolny podzbiór sumujący się do dokładnie t. Należy on do klasy problemów NP-zupełnych, zatem naturalne jest badanie jego algorytmów aproksymacyjnych - takich, które szukają podzbioru sumującego się do co najmniej 1-ε wyniku optymalnego. Aktualnie najlepszy znany algorytm robi to w czasie O(min{n/ε,n+1/ε2 log(1/ε)}). W szczególności nie jest znany żaden algorytm rozwiązujący ten problem w O((n+1/ε)c) dla dowolnego c<2.

Autorzy w pracy pokazują równoważność tego problemu do Min-Plus-Convolution przeprowadzając redukcje w obie strony. Dzięki temu uzyskują algorytm aproksymacyjny dla Subset Sum o poprawionym czasie działania oraz udowadniają, że Subset Sum ma algorytm aproksymacyjny w czasie O((n+1/ε)c) dla c<2 wtedy i tylko wtedy, gdy Min-Plus-Convolution może być rozwiązany w O(nc') dla c'<2. Druga część równoważności jest jednak sprzeczna z hipotezą trudności tego problemu.

Dodatkowo, dla specjalnego wariantu Subset Sum zwanego Partition, autorzy stosują powyższą redukcję otrzymując algorytm aproksymacyjny działający w czasie O(n+1/ε3/2). Jest to pierwszy deterministyczny algorytm z podkwadratową złożonością.

18.11.2021 14:15
Aleksander Katan, Roch Wójtowicz
Filling crosswords is very hard

Autorzy analizują problem wypełniania krzyżówek, który już był rozważany na przykład przez Garey’a i Johnsona w ich książce „Computers and Intractability: A Guide to the Theory of NP-Completeness”. W problemie tym dostajemy m słów i n poziomych lub pionowych slotów (rubryk) oraz jesteśmy proszeni o wypełnienie ich tak, by przecięcia slotów się zgadzały. Autorzy próbują wskazać źródło trudności tej łamigłówki przyglądając się strukturze grafu przecięć slotów. Skupiają się na przypadku, gdy struktura tego grafu przypomina drzewo. Niestety, jeżeli przyjmiemy, że słowa nie mogą być używane wielokrotnie, okazuje się, że problem pozostaje NP-trudny nawet pod bardzo surowymi restrykcjami, jak na przykład, że graf przecięć jest sumą grafów typu star i alfabet ma rozmiar
2, lub że jest matchingiem (krzyżówka składa się z samych rozłącznych krzyży) z alfabetem rozmiaru 3. Zapytanie staje się prostsze, gdy pozwolimy na powtarzanie słów, gdyż autorom udaje się skonstruować algorytm działający w czasie mtw, gdzie tw oznacza treewitdh (szerokość drzewiastą) grafu. Jednak nawet wtedy nie można algorytmu poprawić, by otrzymać FPT. Co więcej, pod założeniem ETH, problem nie może być rozwiązany w czasie mo(k), gdzie k to liczba poziomych slotów instancji problemu.
Zmotywowani tymi przykrymi wynikami, autorzy rozważają bardziej ograniczony przypadek, gdzie parametryzujemy się liczbą slotów wszystkich, a nie tylko poziomych. Problem staje się FPT (o ile alfabet jest stałego rozmiaru), ale złożoność jest wykładnicza od n2. Wykazują, że pod założeniem ETH, nie istnieje algorytm działający w czasie 2o(n^2), nawet dla dwuznakowego alfabetu. Pod koniec pracy rozważana jest wersja optymalizacyjna, w której staramy się wypełnić jak najwięcej pól. Łatwo jest wtedy uzyskać 1⁄2-aproksymację, nawet dla przypadku ważonego, wystarczy po prostu brać pod uwagę tylko pionowe albo tylko poziome sloty. Ten algorytm jest prawdopodobnie optymalny, gdyż istnienie lepszej aproksymacji działającej w wielomianowym czasie przeczyłoby Unique Games Conjecture. Ostatnie dwa wyniki są prawdziwe niezależnie, czy rozpatrujemy przypadek z powtarzaniem słów czy bez.

04.11.2021 14:15
Mateusz Pach, Michał Wronka
Determining 4-edge-connected components in linear time
Prezentujemy pierwszy deterministyczny algorytm obliczający 4-spójne krawędziowo składowe w czasie liniowym. Najpierw pokazujemy algorytm znajdujący wszystkie 3-cięcia krawędziowe w danym grafie 3-spójnym krawędziowo i korzystając z jego wyniku budujemy 4-spójne składowe oryginalnego grafu.
28.10.2021 14:15
Piotr Kaliciak, Kamil Galewski
Turing Completeness and Sid Meier’s Civilization
W pracy zostało wykazane, że trzy gry strategiczne z serii Sid Meier's Civilization: Sid Meier’s Civilization: Beyond Earth, Sid Meier’s Civilization V, i Sid Meier’s Civilization VI, są zupełne w sensie Turinga. Dla każdej gry została pokazana, oparta na jej mechanikach, konstrukcja uniwersalnej maszyny Turinga. Istnienie takich maszyn oznacza, że pod pewnymi założeniami gry te są nierozstrzygalne. Praca pokazuje działanie przykładowej maszyny - Zajętego Bobra złożonego z trzech stanów, zaimplementowanej w jednej z gier.
21.10.2021 14:15
Daniel Bobrzyk, Mateusz Golonka
Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks
10.12.2020 14:15
Jacek Salata, Krzysztof Ziobro
A New Upper Bound for Separating Words
03.12.2020 14:15
Rafał Kilar, Szymon Salabura
Tetris is NP-hard even with O(1) rows or columns
26.11.2020 14:15
Jan Mełech, Michał Zwonek
On the Fine-Grained Complexity of Parity Problems
19.11.2020 14:15
Łukasz Selwa, Juliusz Wajgelt
Compact Distributed Certification of Planar Graphs
12.11.2020 14:15
Dzianis Pivavarau, Dominik Wielgórski
Explicit two-deletion codes with redundancy matching the existential bound
05.11.2020 14:15
Bartłomiej Jachowicz, Mateusz Kaczmarek
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
29.10.2020 14:15
Lech Duraj
Range queries and triangles
22.10.2020 14:15
Marcin Serwin, Wojciech Buczek
A Double-Exponential Lower Bound for the Distinct Vectors Problem
15.10.2020 14:15
Krzysztof Pióro, Krzysztof Potępa
Modular Subset Sum
W problemie Modular Subset Sum dane są liczba naturalna m, n-elementowy multizbiór S liczb całkowitych z zakresu od 0 do m-1 oraz liczba t, dla której chcemy rozstrzygnąć, czy istnieje podzbiór S, który się do niej sumuje modulo m.
 
Przedstawimy własne algorytmy rozwiązujące powyższy problem. Wszystkie z nich będą sprowadzały problem Modular Subset Sum do problemu tekstowego. Na początku przedstawimy prosty algorytm działający w czasie O(n + m*log2(m)) wykorzystujący haszowanie i drzewa przedziałowe. Następnie pokażemy jak poprawić jego złożoność do O(n + m*log(m)). Na końcu zaprezentujemy w pełni deterministyczny wariant algorytmu działający w czasie O(n + m*log(m)*α(m)).
16.01.2020 14:15
Katarzyna Król, Paweł Mader
On the Complexity of Lattice Puzzles [Kobayashi et al.]
Autorzy pracy badają złożoność obliczeniową tradycyjnej łamigłówki zwaną dalej układanką kratową. Celem układanki jest złożenie kraty o wymiarach n×n z 2n płytek z szczelinami.
Łamigówka ta jest powszechnie znanym problemem, niemniej jednak do tej pory nie była ona badana przez informatykę teoretyczną. Autorzy pracy pokazują, że naturalne warianty tej układanki redukują się do podklas w klasie złożoności NP. Jedną z takich podklas jest klasa problemu izomorfizmów grafów GI. O ile wiadomo autorom pracy, jest to pierwszy nietrywialny GI-zupełny problem scharakteryzowany przez klasyczną łamigłówkę.
12.12.2019 14:15
Krzysztof Pióro, Krzysztof Potępa
Linear-Space Data Structures for Range Mode Query in Arrays [Chan, Durocher, Larsen, Morrison, Wilkinson]
Modą multizbioru S nazywamy element, który występuje w S najczęściej, tzn. występuje w S co najmniej tyle razy co każdy inny element S. Mając daną n-elementową tablicę A[1:n] rozważamy prosty problem: konstrukcję statycznej struktury danych pozwalającej szybko odpowiadać na zapytania o modę na przedziale A. Każde zapytanie składa się z pary (i,j), dla której odpowiedzią jest moda A[i:j]. Autorzy pracy prezentują strukturę danych z liniową pamięcią odpowiadającą na zapytania w czasie O(sqrt(n / log n)). Dodatkowo pokazują silną przesłankę, że czas zapytania zdecydowanie niższy od sqrt(n) nie może być uzyskany przy użyciu czysto kombinatorycznych technik - mnożenie macierzy logicznych rozmiaru sqrt(n) x sqrt(n) redukuje się do n zapytań o modę na przedziale w tablicy rozmiaru O(n). Autorzy prezentują też struktury danych dla ortogonalnych zapytań w wyższych wymiarach (zapytania w czasie bliskim O(n1-1/2d)) oraz zapytań o półprzestrzenie (zapytania w czasie O(n1-1/d^2)).
28.11.2019 14:15
Katarzyna Bułat, Dawid Tracz
Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time [P. Parys]

Gry parzystości to gry pomiędzy dwoma graczami (zwyczajowo Even oraz Odd) na grafie skierowanym G = (V, E). Gracze przesuwają między wierzchołkami wirtualny token, tworząc ścieżkę. Wierzchołki grafu są etykietowane liczbami naturalnymi i każdy z nich jest przypisany do jednego gracza, który decyduje w jakim kierunku zostanie wykonany ruch z tego wierzchołka. Celem każdego z graczy jest wybranie takiej strategii, że przy nieskończonej grze (ścieżce), najwyższa nieskończenie wiele razy powtarzająca się etykieta będzie odpowiednio parzysta bądź nieparzysta.

Problem gry parzystości jest deterministyczny, to znaczy dla każdego wierzchołka jeden z graczy posiada strategię wygrywającą. Rekurencyjny algorytm Zielonki rozwiązuje grę parzystości w czasie wykładniczym. Istnieje jednak algorytm działający w czasie quasi-wielomianowym, czyli 2O((log(n))^c) dla pewnego, ustalonego c.

W trakcie prezentacji omówiony zostanie schemat nowej wersji algorytmu, przeprowadzona analiza jego złożoności oraz przedstawiony dowód poprawności zwracanego przez niego wyniku.

21.11.2019 14:15
Jędrzej Kula, Przemysław Simajchel
Subtree Isomorphism Revisited [A. Abboud et al.]

Problem Izomorfizmu Poddrzew zadaje pytanie, czy dane drzewo zawarte jest w innym danym drzewie. Ten problem o zasadniczym znaczeniu dla algorytmiki jest badany już od lat 60. ubiegłego wieku. Podkwadratowe algorytmy znane są dla niektórych wariantów, np. drzew uporządkowanych, ale nie w ogólnym przypadku.

Poprzez redukcję z problemu Wektorów Ortogonalnych pokażemy, że prawdziwie podkwadratowy algorytm dla Izomorfizmu Poddrzew przeczy SETH. Dodatkowo pokażemy, że to samo ograniczenie dolne utrzymuje się również w przypadku ukorzenionych drzew o logarytmicznej wysokości. W opozycji do niego zaprezentujemy również podkwadratowy algorytm randomizowany dla drzew o stałym stopniu i logarytmicznej wysokości.

Redukcja korzysta z nowych "gadżetów drzewowych", które prawdopodobnie przydadzą się w przyszłości w wyznaczaniu ograniczeń dolnych opartych na SETH dla problemów na drzewach. Algorytmy opierają się na znanych wynikach o złożoności randomizowanych drzew decyzyjnych.

07.11.2019 14:15
Nicoll Bryła, Mateusz Pabian
Faster Algorithms for All Pairs Non-Decreasing Paths Problem [Duan, Jin, Wu]
W tej pracy autorzy prezentują poprawiony algorytm dla problemu wszystkich par ścieżek niemalejących (APNP) dla grafów prostych, skierowanych i ważonych o czasie działania Õ(n^((3+ω)/2)) = Õ(n^2,686), gdzie n jest liczbą wierchołków, a ω jest wykładnikiem złożoności algorytmu szybkiego mnożenia macierzy z pracy [Williams 2012, Le Gall 2014]. To odpowiada najlepszemu, obecnemu górnemu ograniczeniu dla (max, min)-iloczynu macierzy, który można zredukować do APNP. Następne usprawnienia dla APNP implikują szybszy algorytm dla (max, min)-iloczynu macierzy. Poprzednie najlepsze oszacowanie górne dla ważonych, skierowanych grafów było Õ(n^(1/2(3+(3-ω)/(ω+1) + ω))) = Õ(n^2,78) [Duan, Gu, Zhang 2018]. Autorzy pokazują również algorytm Õ(n^2) dla APNP w nieskierowanych, prostych grafach, który również osiąga optimum z czynnikiem logarytmicznym.
17.10.2019 14:15
Piotr Helm, Krzysztof Zysiak
Optimal Sorting with Persistent Comparison Errors [B. Geissmann et al.]
Rozważamy problem sortowania n elementów w przypadku stałego błędu porównań. W tym problemie, każde porównanie między dwoma elementami może się pomylić ze stałym (małym) prawdopodobieństwem, i porównania nie mogą zostać powtórzone. Perfekcyjne posortowanie w tym modelu jest niemożliwe i celem jest zminimalizowanie dyslokacji każdego z elementów w zwróconym ciągu, czyli odległość od jego poprawnej pozycji. Istniejące ograniczenia dolne dla tego problemu pokazują, że żaden algorytm nie zagwarantuje z wysokim prawdopodobieństwem maksymalnej i sumarycznej dyslokacji lepszej niż Ω(logn) i Ω(n), odpowiednio, bez względu na czas działania.
W tej pracy, prezentujemy pierwszy sortujący algorytm o złożoności O(n log n), który gwarantuje zarówno maksymalna dyslokację O(log n), jak i sumaryczną dyslokację O(n) z wysokim prawdopodobieństwem. To rozstrzyga złożoność czasową tego problemu i pokazuje, że błędy porównań nie zwiększają jego złożoności czasowej: ciąg z najlepszą możliwą dyslokacją może zostać uzyskany w czasie O(n logn), i nawet bez błędów porównań czas Ω(n log n) jest konieczny, by zagwarantować takie ograniczenia dyslokacji.
Aby osiągnąć ten optymalny wynik, rozwiązujemy dwa podproblemy, za pomocą metod, które mogą mieć dalsze, osobne zastosowania. Jednym z nich jest zlokalizowanie pozycji, na którą należy wstawić element do prawie posortowanego ciągu o dyslokacji O(log n)  w taki sposób, aby dyslokacja zwracanego ciągu wciąż była O(logn). Drugi problem - jak równocześnie wstawić m elementów w prawie posortowany ciąg innych m elementów, tak aby zwracany ciąg 2m elementów pozostał prawie posortowany.
10.10.2019 14:15
Bartłomiej Jachowicz, Mateusz Kaczmarek
Separating strings with small automata [J.M.Robson]

Tematem pracy jest problem znalezienia automatu skończonego rozróżniającego dwa łańcuchy o możliwie najmniejszej liczbie stanów. Autorzy pokazują, że dla łańcuchów ograniczonych przez długość n istnieje automat akceptujący tylko jeden z łańcuchów o O(n2/5 * log3/5n) stanach, co dla przypadku, gdy łańcuchy na wejściu są równej długości jest najlepszym znanym ograniczeniem.

 

24.04.2019 14:00
Bartłomiej Jachowicz, Mateusz Kaczmarek
On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree (M. Equi et al.)
Szukanie dokładnego wzorca w grafie etykietowanym to problem polegający na szukaniu ścieżek w grafie G = (V, E), których etykiety tworzą napis taki sam jak wzorzec P[1…m]. Ten problem można rozwiązać za pomocą algorytmu działającego w kwadratowym czasie O(|E|m). Jednakże w tej pracy, autorzy podają warunkowe ograniczenie dolne na czas działania algorytmu. Przy założeniu Strong Exponential Time Hypothesis (SETH) nie istnieje algorytm działający w czasie O(m |E|1-e) lub  O(|E| m1-e) dla dowolnej stałej e > 0.
 
17.04.2019 14:00
Rafał Kaszuba, Michał Zwonek
A simpler implementation and analysis of Chazelle’s Soft Heaps (H. Kaplan, U. Zwick)
W 2000 roku Chazelle wymyślił nową strukturę danych:  aproksymacyjne priorytetowe kolejki złączalne (Soft Heaps) i użył jej aby uzyskać najszybszy znany deterministyczny algorytm oparty na porównaniach do obliczenia minimalnego drzewa rozpinającego, jak również nowe algorytmy do znajdowania k-tej najmniejszej liczby na liście i przybliżonego sortowania. Jeśli wstawimy do kolekcji miękkich kopców n elementów to co najwyżej εn ze wszystkich elementów będących aktualnie w kopcach dla danego parametru ε może być uszkodzonych, to znaczy ich klucze zostały sztucznie podwyższone. Dzięki pozwoleniu na uszkodzenia każda operacja na miękkim kopcu jest wykonywana w O(log 1/ε) amortyzowanym czasie. Chazelle uzyskał miękkie kopce  przy pomocy kopców dwumianowych, gdzie każda kolejka priorytetowa to kolekcja drzew dwumianowych. W tej pracy autorzy opisują prostszą i bardziej bezpośrednią implementację miękkich kopców, gdzie każda kolejka priorytetowa jest złożona z kolekcji standardowych drzew binarnych. Ta implementacja ma przewagę nad wcześniejszą, bo nie trzeba wykonywać operacji sprzątania, której używał Chazelle w swojej. W pracy przedstawiona jest również zwięzła analiza amortyzowana nowej implementacji.
13.03.2019 14:15
Kornel Dulęba, Jan Mełech
A Randomized Maximum-Flow Algorithm (Cheriyan & Hagerup)

Praca przedstawia randomizowany algorytm obliczający maksymalny przepływ. Dla sieci przepływowej o n wierzchołkach i m krawędziach, czas wykonania jest O(nm + n2(log n)2) z prawdpodobieństwem co najmniej 1 - 2-sqrt(nm). Algorytm jest zawsze poprawny i w najgorszym przypadku działa w czasie O(nm log n). Czynnik randomizujący składa się tylko z zastosowania losowych permutacji do list sąsiedztwa wierzchołków na początku algorytmu.

24.01.2019 14:00
Jan Derbisz, Franciszek Stokowacki
An Equivalence Class for Orthogonal Vectors (L.Chen, R.Williams)
Problem sprawdzania, czy pośród n wektorów istnieje para wektorów ortogonalnych umiemy łatwo rozwiązać w czasie O(n2 log n), jednak nie jest znany algorytm szybszy niż n2. Autorzy pracy dowodzą, że istnienie algorytmu podkwadratowego jest równoważne istnieniu takich algorytmów dla kilku innych problemów, między innymi Apx-Min-IP - znajdowania pary wektorów będących k-aproksymacją maksymalnego iloczynu skalarnego oraz Approximate Bichrom.-ℓp-Closest-Pair - problemu znajdowania aproksymowanej najbliższej dwukolorowej pary punktów. Powyższe równoważności są zachowane w sytuacji, w której zamiast odpowiadać offline mamy strukturę danych i odpowiadamy na zapytania online. Dodatkowo w pracy przedstawione są nowe algorytmy aproksymowane dla Apx-Min-IP oraz rozwiązywania pewnych instancji MAX-SAT.
17.01.2019 14:00
Katarzyna Bułat, Kamil Rajtar
Correctness of constructing optimal alphabetic trees reviseted

Prezentowana przez nas praca przedstawia nowe obserwacje, które pozwoliły autorom dowieść poprawności dwóch znanych algorytmów (Hu-Tuckera i Garsi-Wachs) na konstrukcję optymalnych drzew utrzymujących porządek leksykograficzny. Omówimy uogólnioną wersję algorytmu Garsi-Wachs wraz z przejrzystym i łatwym do zilustrowania dowodem, który pomaga również w zrozumieniu podejścia Hu-Tuckera.

10.01.2019 14:00
Bartłomiej Jachowicz, Mateusz Kaczmarek
SETH-based Lower Bounds for Subset Sum and Bicriteria Path
Głównym rezultatem tego artykułu jest ścisła redukcja z k-SAT do problemu Subset Sum na gęstych instancjach, co pokazuje że algorytm Bellmana z 1962 roku O*(T) - dla Subset Sum z n liczbami i celem równym T nie da się poprawić do czasu T1 - e * 2o(n), dla dowolnego e > 0, pod warunkiem prawdziwości SETH.
Wnioskiem z tego jest twierdzenie "Direct-OR" dla problemu Subset Sum pod warunkiem prawdziwości SETH, dające nowe możliwości udowadniania dolnych ograniczeń. Daje nam to możliwość założenia, że podjęcie decyzji o tym, czy jedna z N danych instancji problemu Subset Sum jest TAK-instancją wymaga (NT)1-o(1) czasu. Zastosowaniem danego rezultatu jest dolne ograniczenie dla problemu BICRITERIA s,t-PATH pod warunkiem prawdziwośći SETH.
03.01.2019 14:00
Rafał Kaszuba, Krzysztof Zysiak
Fast Modular Subset Sum using Linear Sketching

Dostając zbiór n dodatnich liczb całkowitych, problem Modular Subset Sum polega na sprawdzeniu czy istnieje podzbiór, który sumuje się do zadanego t modulo dana liczba całkowita m. Jest to naturalne uogólnienie problemu Subset Sum (m=+∞), który silnie łączy się z addytywną kombinatoryką i kryptografią.

Niedawno zostały opracowane efektywne algorytmy dla przypadku niemodularnego, działające w czasie blisko-liniowym pseudo-wielomianowym. Jednak dla przypadku modularnego najlepszy znany algorytm (Koiliaris'a i Xu) działa w czasie Õ(m5/4).

W tej pracy prezentujemy algorytm działający w czasie Õ(m), który dopasowuje się do warunkowego ograniczenia dolnego opartego na SETH. W przeciwieństwie do większości poprzednich wyników związanych z problemem Subset Sum, nasz algorytm nie korzysta z FFT. Natomiast, jest zdolny zasymulować "podręcznikowe" programowanie dynamiczne znacznie szybciej, używając pomysłów ze Szkicowania Liniowego. Jest to jedna z pierwszych aplikacji technik bazujących na szkicowaniu, by osiągnąć szybki algorytm dla problemów kombinatorycznych w modelu offline.

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