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.

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:
- Õ(u²+t) dla all-target change-making w oparciu o twierdzenie Erdősa i Grahama dotyczące problemu Frobeniusa;
- Õ(u²+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.

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 I_s, I_t i chcemy stwierdzić czy istnieje sekwencja I₁, …, I_s zbiorów niezależnych w G taka, że I₁ = I_s, I_l = I_t oraz I_i ∆ I_i+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).

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(2^o(n)). Omawia także algorytm programowania dynamicznego rozwiązujący planszę gry, opierający się na strukturach Catalana.

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.

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.

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(n^2.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(n³) 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. 

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.

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/ε² 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(n^c') 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ą.

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 m^tw, 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 m^o(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 n². Wykazują, że pod założeniem ETH, nie istnieje algorytm działający w czasie 2^{o(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.

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 2^{O((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.

The Subtree Isomorphism problem asks whether a given tree is contained in an another given tree. The problem is of fundamental importance and has been studied since the 1960s. Subquadratic algorithms are known for some variants, e.g. ordered trees, but not in the general case.

We will present a reduction from the Orthogonal Vectors problem to Subtree Isomorphism, showing that a truly subquadratic algorithm for the latter refutes the SETH. In addition, we will show that the same lower bound holds even for the case of rooted trees of logarithmic height. To contrast the lower bound, we will also show subquadratic randomized algorithms for rooted trees of constant degree and logarithmic height.

The reductions utilize the new "tree gadgets" that are likely useful for future SETH-based lower bounds for problems on trees. The algorithms apply a folklore result from randomized decision tree complexity.

The main problem considered in this paper is to find the smallest finite automaton seperating two strings. Authors prove that, for strings of length bounded by n, there exists an automaton with O(n^2/5 * log^3/5n) states, accepting only one of given strings, which in the case of two strings with the same length is the best known result.

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.

The main result of this paper is a tight reduction from k-SAT to Subset Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial O*(T) - time algorithm for Subset Sum on n numbers and target T cannot be improved to time T^{1 - e} * 2^o(n) for any e > 0, unless SETH fails.
As a corollary it proves a "Direct-OR" theorem for Subset Sum under SETH, offering new tool for proving conditional lower bounds. It is now possible to assume that deciding whether one out of N given instances of Subset Sum is a YES instances requires time (NT)^1-o(1). As an application of this corollary, we prove a tight SETH - based lower bound for classical BICRITERIA s,t - PATH problem.

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 Õ(m^5/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.

In 2015, Abboud, Backurs and Vassilevska-Williams showed that an O(n2-eps) time algorithm for LCS would refute the Strong Exponential Time Hypothesis (SETH). In this paper, authors prove conditional lower bounds of the form O(n2/logc n) for LCS, as well as for Frechet Distance and regular expression pattern matching. The main result is an efficient reduction from SAT on formulas on n variables and size s, to LCS on words of length 2n/2s1+o(1). It follows that an O(n2/log7+epsn) algorithm for LCS would refute some plausible conjectures about Formula-SAT, and an O(n2/log17+epsn) algorithm would result in major progress in theory of circuit complexity.

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)).

We consider a tree with n vertices. On vertex number x there is a box with label p(x), with the function p being a permutation of {1,2,...,n}. A robot is walking on the tree, carrying at most one box at a time. If a box is placed where robot is standing, it can swap this box with the one being carried. The robot's goal is to sort the boxes, placing each one at the vertex with its number. The paper by D. Graf gives an algorithm computing the shortest possible robot's walk in quadratic time, as well as the proof that the problem becomes NP-complete if planar graphs are considered instead of trees.

In 2006, a celebrated result by Mucha and Sankowski stated that the maximum matching problem can be done by Gaussian elimination. The complexity of this algorithm depends on matrix multiplication, but certainly beats O(n^2.5) long-standing record of Micali-Vazirani algorithm.

In recent years, some new algorithms for matrix multiplication problem were presented. Each of them is, however, only slightly faster than previous ones, while requiring substantially more complex analysis. Because of this, the long-standing question of optimal matrix multiplication algorithm seems even harder.

In my presentation, a short survery of the matrix multiplication algorithm is given. The presentation is based on François Le Gall's survey lecture of 2014.

The paper by Aleksander Mądry describes a new approach to the maximum flow problem. We define an electrical flow by assigning resistances to every edge and minimizing total energy instead of maximizing flow. Any flow network can be reduced to some electrical flow problem, using auxiliary reductions to some bipartite matching problems. The main result is a new maximum flow algorithm, working in O(m10/7). The presentation will cover a simpler, O(m3/2) version of the algorithm.

The paper, resolves a long-standing open question: is the greedy approach for Steiner forest problem optimal up to multiplicative constant? The result by Anupam Gupta and Amit Kumar proves that in fact it is, with constant being at most 96. While some approximation algorithms for this problem, using linear programming, were previously known, this is the first known bound for a greedy algorithm.

The presented paper (by J. Łącki and A. Karczmarz) deals with graph timelines - graphs with edges being created and destroyed over time. There is an effective algorithm for answering queries about reachability (finding a path between two given vertices) and biconnectivity (two disjoint paths) over some given time intervals.

The O(n log n) lower bound for sorting is valid only if the sorted objects allow no operations except comparing. For sorting integers, the bound can be broken - Mikkel Thorup's result of 1997 shows an O (n (log log n)²) algorithm for sorting arbitrary integers.

The most popular version of Find-Union algorithm uses path compression and linking by rank. The presented work of Goel, Khanna, Larkin and Tarjan gives an analysis of the same algorithm, but with arbitrary (randomized) linking.

Counting all matchings in a given graph is a #P-complete problem. However, for planar graphs it can be done in polynomial time. The FKT algorithm does it by exploiting the connection between the notions of matrix determinant and matrix permanent.