The reductions utilize the new "tree gadgets" that are likely useful for future SETH-based lower bounds for problems on trees. To contrast the lower bound, we will also show subquadratic randomized algorithms for rooted trees of constant degree and logarithmic height. In addition, we will show that the same lower bound holds even for the case of rooted trees of logarithmic height. 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. ordered trees, but not in the general case. Subquadratic algorithms are known for some variants, e.g. The problem is of fundamental importance and has been studied since the 1960s. The Subtree Isomorphism problem asks whether a given tree is contained in an another given tree. 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. Istnieje jednak algorytm działający w czasie quasi-wielomianowym, czyli 2 O((log(n))^c) dla pewnego, ustalonego c. Rekurencyjny algorytm Zielonki rozwiązuje grę parzystości w czasie wykładniczym. Problem gry parzystości jest deterministyczny, to znaczy dla każdego wierzchołka jeden z graczy posiada strategię wygrywającą. 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. 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. Gracze przesuwają między wierzchołkami wirtualny token, tworząc ścieżkę. Gry parzystości to gry pomiędzy dwoma graczami (zwyczajowo Even oraz Odd) na grafie skierowanym G = (V, E). Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time Additionally, we give linear-space data structures for orthogonal range mode in higher dimensions (queries in near O(n 1−1/2d) time) and for halfspace range mode in higher dimensions (queries in O(n 1−1/d^2) time). Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely combinatorial techniques we show that boolean matrix multiplication of two sqrt(n) x sqrt(n) matrices reduces to n range mode queries in an array of size O(n). We improve their result and present an O(n)-space data structure that supports range mode queries in O(sqrt(n/log n)) worst-case time. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires O(sqrt(n)*log log n) query time. Each query consists of an input pair of indices (i,j) for which a mode of A must be returned. Given an array A of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Linear-Space Data Structures for Range Mode Query in Arrays Ī mode of a multiset S is an element a ∈ S of maximum multiplicity that is, a occurs at least as frequently as any other element in S. Like the sliding block puzzles, this simple puzzle can be used to characterize several representative computational complexity classes. As far as the authors know, this is the first non-trivial GI-complete problem characterized by a classic puzzle. That is, the variant is GI-complete in general. Especially, one of the natural variants gives a characterization of the graph isomorphism problem. This puzzle has some natural variants, and they characterize representative computational complexity classes in the class NP. It has a long history in the puzzle society however, there is no known research from the viewpoint of theoretical computer science. A lattice puzzle consists of 2n plates with some slits, and the goal of this puzzle is to assemble them to form a lattice of size n×n. In this paper, authors investigate the computational complexity of lattice puzzle, which is one of the traditional puzzles.