Termine Vorträge (Archiv)

Treffer 101 - 150 von 152 Ergebnissen

  • Termin
     
    Titel
  • 26.09.2017
    10:00 - 11:00
     
    Succinct Counting and Progress Measures for Solving Infinite Games// Katrin Dannert
    The talk will be given in English.
  • 26.09.2017
    11:00 - 12:00
     
    Verfahren zur Übersetzung von regulären Ausdrücken in endliche Automaten
    Daniel Schmitz
  • 13.09.2017
    11:00 - 12:00
     
    A finitary analogue of the downward Lowenheim-Skolem property
    Abhisekh Sankaran
    We present a model-theoretic property of finite structures, that can be seen to be a finitary analogue of the well-studied downward Lowenheim-Skolem property from classical model theory. We call this property the *equivalent bounded substructure property*, denoted EBSP. Intuitively, EBSP states that a large finite structure contains a small ``logically similar'' substructure, where logical similarity means indistinguishability with respect to sentences of FO/MSO having a given quantifier nesting depth. It turns out that this simply stated property is enjoyed by a variety of classes of interest in computer science: examples include regular languages of words, trees (unordered, ordered, ranked or partially ranked) and nested words, and various classes of graphs, such as cographs, graph classes of bounded tree-depth, those of bounded shrub-depth and m-partite cographs. Further, EBSP remains preserved in the classes generated from the above using various well-studied operations, such as complementation, transpose, the line-graph operation, disjoint union, join, and various products including the Cartesian and tensor products. All of the aforementioned classes admit natural tree representations for their structures. We use this fact to show that the small and logically similar substructure of a large structure in any of these classes, can be computed in time linear in the size of the tree representation of the structure, giving linear time fixed parameter tractable (f.p.t.) algorithms for checking FO/MSO definable properties of the large structure. We conclude by presenting a strengthening of EBSP, that asserts ``logical self-similarity at all scales'' for a suitable notion of scale. We call this the *logical fractal* property and show that most of the classes mentioned above are indeed, logical fractals.
  • 01.09.2017
    10:00 - 11:00
     
    FO Model Checking on some Dense Graph Classes using FO-Interpretations
    Dimitri Rusin
  • 01.09.2017
    10:00 - 11:00
     
    FO Model Checking on some Dense Graph Classes using FO-Interpretations
    Dimitri Rusin
  • 31.08.2017
    12:00 - 12:30
     
    Definierbarkeit abelscher Summationsprobleme in Fixpunktlogiken und TC-Logiken
    Yannic Rohde
  • 31.08.2017
    12:00 - 12:30
     
    Definierbarkeit abelscher Summationsprobleme in Fixpunktlogiken und TC-Logiken
    Yannic Rohde
  • 30.08.2017
    11:00 - 12:00
     
    Homomorphisms are a good basis for counting small subgraphs
    Holger Dell
    We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. Using the framework of graph motif parameters, we obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G: For graphs H on k edges, we show how to count subgraph copies of H in time k^{O(k)}⋅n^{0.174k+o(k)} by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k+c) time for k-edge matchings or O(n0.46k+c) time for k-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating f∈C on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G, where H is from a fixed class H, we want to count color-preserving H-copies in G. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions. Joint work with Radu Curticapean and Dániel Marx
  • 30.08.2017
    11:00 - 12:00
     
    Homomorphisms are a good basis for counting small subgraphs
    Holger Dell
    We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. Using the framework of graph motif parameters, we obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G: For graphs H on k edges, we show how to count subgraph copies of H in time k^{O(k)}⋅n^{0.174k+o(k)} by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k+c) time for k-edge matchings or O(n0.46k+c) time for k-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating f∈C on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G, where H is from a fixed class H, we want to count color-preserving H-copies in G. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions. Joint work with Radu Curticapean and Dániel Marx
  • 25.08.2017
    15:00 - 16:00
     
    Decomposition Techniques for the Graph Isomorphism Problem
    Oliver Feith
    Closing the gap between the lower and upper bounds for the computational complexity of the Graph Isomorphism problem still is a big challenge for mathematicians and computer scientists. While resolving this problem in the general case seems out of reach, substantial progress has been made for restricted graph classes such as planar graphs. In particular, planar graph isomorphism has recently been shown to be in L (and thus is L-complete) by Datta, Limaye, Nimbhorkar, Thierauf and Wagner. We generalize the decomposition technique used in their result to work with minor-closed graph classes whose 3-connected members fulfill a fixability condition and admit a log-space canonization algorithm.
  • 24.08.2017
    10:30 - 10:30
     
    Weisfeiler-Lehman Kernels for Deep Neural Nets
    Jan Tönshoff
    Many real world applications, such as analysing social networks or internet traffic, require the analysis of large sets of graph structured data. Teaching neural networks to recognise patterns in graphs seems like an intuitive way of simplifying these tasks. To achieve this, we need to represent graphs as vectors in a suitable way that enables neural networks to find patterns in the underlying structure of the graphs. In this thesis we examine the performance of a vector representation for graphs obtained from the Weisfeiler-Lehman subtree kernel as an input for neural networks. We test the performance on standard graph classification tests with datasets based in bioinformatics. The results are shown to be competitive with those of state-of-the-art graph kernels for support vector machines. To solve scalability problems, we show that the size of these vectors can be reduced significantly without lowering the learning performance. Additionally, we show that the adjacency matrix is not a suitable vector representation of graphs when using neural networks. While the networks are able to learn some patterns with these inputs, the learning performance is significantly lower than for the vectors from the Weisfeiler-Lehman subtree kernel. Before we make these observations we provide brief introductions into Weisfeiler-Lehman graph kernels and neural networks.
  • 14.08.2017
    11:00 - 12:00
     
    Algorithms computing the fixing number of planar graphs
    Daniel Mock
    Fixing sets are a way to break symmetries and determine automorphisms of a graph. The fixing number of a graph G is the smallest cardinality of a set of vertices S such that only the trivial automorphism of G fixes every vertex in S. In this talk I present an algorithm for computing the fixing number of a planar graph by decomposing it into its triconnected components and by using bottom-up recursion upon these components. For this to work I introduce a generalization of the fixing number, the so-called vertex-arc fixing number: in addition to vertices, the fixing set may also contain edges and arcs of the graph. The provided algorithm can be applied to any minor-closed graph class that allows isomorphism testing and computing the vertex-arc fixing number of its triconnected graphs in polynomial time.
  • 28.07.2017
    10:15 - 11:45
    ATI
    Fixed-Parameter Tractable Canonization for Graphs of Bounded Treewidth
    Daniel Wiebking
  • 27.07.2017
    11:00 - 12:00
     
    Comparing the power of advice strings
    Gaëtan Douéneau
    We investigate a certain notion of comparison between infinite words. In a general way, if M is a model of computation (e.g. Turing machines) and C a class of objects (e.g. languages), the complexity of an infinite word w can be measured with respect to the objects from C that are presentable with machines from M using w as an advice. In our case, the model is finite automata and the objects are either recognized languages or presentable structures, known respectively as advice regular languages and advice automatic structures. This leads to several different classifications that are studied in detail; logical and computational equivalent characterizations are derived. Our main results explore the connections between classes of advice automatic structures, $MSO$-transductions and two-way transducers.
  • 21.07.2017
    10:15 - 11:45
    ATI
    An Improved Distributed Algorithm for Maximal Independent Set
    work by Mohsen Ghaffari
  • 20.07.2017
    14:00 - 15:00
     
    Graph Classification: Kernels and Beyond
    Christopher Morris
    Graph kernels are a popular approach to graph comparison and at the heart of many machine learning applications in bioinformatics, imaging, and social-network analysis. In this talk we shall first present a graph kernel that takes "local" and "global" graph properties into account. Thereto, we develop a "local" version of the $k$-dimensional Weisfeiler-Lehman algorithm. In order to make our kernel scalable, we devise a randomized version of the kernel with provable approximation guarantees using conditional Rademacher averages. On bounded-degree graphs, it can even be computed in constant time. In the second part, we will give an overview about recent progress in the area of graph classification and graph regression via so called "deep learning".
  • 19.07.2017
    16:00 - 17:00
     
    Stochastic dominance and the bijective ratio of online algorithms
    Spyros Angelopoulos
    Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. Accordingly this holds for bijective analysis, which can be interpreted as stochastic dominance assuming the uniform distribution over requests. These techniques have been applied to some online problems, and have provided a clear separation between algorithms whose performance varies significantly in practice. However, there are situations in which they are not readily applicable due to the fact that they stipulate a stringent relation between the compared algorithms. In this presentation, we propose remedies for these shortcomings. Our contribution is two-fold. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the bijective ratio as a natural extension of (exact) bijective analysis. This renders the concept of bijective analysis (and that of stochastic dominance) applicable to all online problems, and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous k-server problem on metrics such as the line, the circle, and the star. Joint work with Marc Renault and Pascal Schweitzer
  • 18.07.2017
    15:00 - 15:30
     
    Fractional Hypertree Decompositions
    Steffen van Bergerem
  • 07.07.2017
    10:15 - 11:15
    ATI
    Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
    work by Ran Raz
  • 07.07.2017
    11:15 - 12:15
     
    Enumerating Tree Decompositions: Why and How
    Benny Kimelfeld
    Many intractable problems on graphs have efficient solvers when graphs are trees or forests. Tree decompositions often allow to apply such solvers to general graphs by grouping nodes into bags laid out in a tree structure, thereby decomposing the problem into the sub-problems induced by the bags. This approach has applications in a plethora of domains, partly because it allows the optimize inference on probabilistic graphical models, as well as evaluation of database queries. Nevertheless, a graph can have exponentially many tree decompositions and finding an ideal one is challenging, for two main reasons. First, the measure of goodness often depends on subtleties of the specific application at hand. Second, theoretical hardness is met already for the simplest measures such as the maximal size of bag (a.k.a. “width”). Therefore, we explore the approach of producing a large space of high-quality tree decompositions for the application to choose from. I will describe our application of tree decompositions in the context of “worst-case optimal” joins --- a new breed of in-memory join algorithms that satisfy strong theoretical guarantees and were found to feature a significant speedup compared to traditional approaches. Specifically, I will explain how this development led us to the challenge of enumerating tree decompositions. Then, I will describe a novel enumeration algorithm for tree decompositions with a theoretical guarantee on the delay (the time between consecutive answers), and an experimental study thereof (on graphs from various relevant domains). Finally, I will describe recent results that provide guarantees on both the delay and the quality of the generated tree decompositions. The talk will be based on papers that appeared in EDBT 2017 and PODS 2017, co-authored with Nofar Carmeli, Yoav Etsion, Oren Kalinsky and Batya Kenig.
  • 04.07.2017
    16:00 - 17:00
     
    The hardness of embedding grids and walls
    Yijia Chen
    The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph G from some class K of ``pattern graphs'' can be embedded into a given graph H (that is, is isomorphic to a subgraph of H) is fixed-parameter tractable if K is a class of graphs of bounded tree width and W[1]-complete otherwise. In this talk, I will explain the background and history of this conjecture, and also our recent result that the embedding problem is W[1]-complete if K is the class of all grids or the class of all walls. This is joint work with Martin Grohe and Bingkai Lin.
  • 04.07.2017
    17:00 - 18:00
     
    Testing logically defined properties on structures of bounded degree
    Isolde Adler
    Property testing (for a property P) asks for a given input, whether it has property P, or is "far" from having that property. A "testing algorithm" is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as "extremely efficient", making them relevant in the context of big data. We extend the bounded degree model of property testing from graphs to relational structures, and we show that every property definable in first-order logic is testable with a constant number of queries in constant time. On structures of bounded tree-width, monadic second-order logic can be tested with a constant number of queries in polylogarithmic time. This is joint work with Frederik Harwath.
  • 30.06.2017
    10:15 - 11:45
    ATI
    Regular Separability of One Counter Automata
    work by Wojciech Czerwiński and Sławomir Lasota
  • 30.06.2017
    10:15 - 11:45
    ATI
    Regular Separability of One Counter Automata
    work by Wojciech Czerwiński and Sławomir Lasota
  • 23.06.2017
    10:15 - 11:45
    ATI
    The 4/3 Additive Spanner Exponent Is Tight
    work by Amir Abboud and Greg Bodwin
  • 16.06.2017
    10:15 - 11:45
    ATI
    The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
    Sandra Kiefer
    We prove that the Weisfeiler-Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in fixed- point logic with counting using at most 4 variables. The previously best known upper bounds for the dimension and number of variables were 14 and 15, respectively. First we show that, for dimension 3 and higher, the WL-algorithm correctly tests isomorphism of graphs in a minor-closed class whenever it determines the orbits of the automorphism group of any vertex-/arc-colored 3-connected graph belonging to this class. Then we prove that, apart from several exceptional graphs (which have WL-dimension at most 2), the individualization of two correctly chosen vertices of a colored 3-connected planar graph followed by the 1-dimensional WL-algorithm produces the discrete vertex partition. This implies that the 3-dimensional WL-algorithm determines the orbits of a colored 3-connected planar graph. As a byproduct of the proof, we get a classification of the 3-connected planar graphs with fixing number 3. This is joint work with Ilia Ponomarenko and Pascal Schweitzer.
  • 02.06.2017
    10:15 - 11:45
    ATI
    A Purely Relational Language for Choiceless Computation
    Erkal Selman
  • 02.06.2017
    10:15 - 11:45
    ATI
    A Purely Relational Language for Choiceless Computation
    Erkal Selman
  • 30.05.2017
    10:30 - 11:30
     
    The Connection Between Visibly Pushdown and Operator Precedence Languages
    Mietze Tang
    Bachelor thesis final talk
  • 30.05.2017
    10:30 - 11:30
     
    The Connection Between Visibly Pushdown and Operator Precedence Languages
    Mietze Tang
    Bachelor thesis final talk
  • 19.05.2017
    10:15 - 11:45
    ATI
    Graph decompositions using MSO transductions
    Marlin Frickenschmidt
  • 17.05.2017
    15:30 - 16:30
     
    Answering database queries under updates
    Nicole Schweikardt
    Query evaluation is one of the most fundamental tasks in databases, and a vast amount of literature is devoted to the complexity of this problem. This talk will focus on query evaluation in the “dynamic setting”, where the database may be updated by inserting or deleting tuples. In this setting, an evaluation algorithm receives a query Q and an initial database D and starts with a preprocessing phase that computes a suitable data structure to represent the result of evaluating Q on D. After every database update, the data structure is updated so that it represents the result of evaluating Q on the updated database. The data structure shall be designed in such a way that it quickly provides the query result, preferably in constant time (i.e., independent of the database size). We focus on the following flavours of query evaluation. (1) Testing: Decide whether a given tuple t is contained in Q(D). (2) Counting: Compute the number of tuples that belong to Q(D). (3) Enumeration: Enumerate Q(D) with a bounded delay between the output tuples. Here, as usual, Q(D) denotes the k-ary relation obtained by evaluating a k-ary query Q on a relational database D. For Boolean queries, all three tasks boil down to (4) Answering: Decide if Q(D) is non-empty. Compared to the dynamic descriptive complexity framework introduced by Patnaik and Immerman (1997), which focuses on the expressive power of first-order logic on dynamic databases and has led to a rich body of literature, we are interested in the computational complexity of query evaluation. We say that a query evaluation algorithm is efficient if the update time is either constant or at most polylogarithmic in the size of the database. In this talk I want to give an overview of recent results in this area.
  • 12.05.2017
    10:15 - 11:45
    ATI
    Learning MSO-definable hypotheses on strings
    Martin Ritzert
  • 05.05.2017
    10:15 - 11:45
    ATI
    Tree Automata with Constraints for Infinite Trees
    Patrick Landwehr
  • 28.04.2017
    10:15 - 11:45
    ATI
    On the Expressiveness of Unfolding Proofs for Recursive Data Structures
    Christof Löding
    Unfolding proofs are a heuristic that is used for verifying properties of heap manipulating programs with recursively defined data structures (like lists or trees). The heuristic reduces the property to be verified to a finite set of quantifier formulas, which can be tested for satisfiability by an SMT solver. The quantifier formulas are basically obtained by instantiating (unfolding) the recursive definitions with concrete terms referring to heap elements. In this joint ongoing work with P. Madhusudan and Lucas Pena (University of Illinois Urbana-Champaign), we aim at understanding which properties can proven using this heuristic.
  • 25.04.2017
    10:30 - 11:30
     
    Complexity of cardinality problems for automata on infinite words
    Duc Thanh Tran
    Bachelor thesis final talk
  • 21.04.2017
    11:45 - 12:45
     
    Complexity of determinizing automata by pruning the transition relation
    Philip Tse
    Bachelor thesis final talk
  • 29.03.2017
    10:00 - 11:00
     
    Complexity of the Graph Homomorphism Problem
    Philipp Niemietz
  • 29.03.2017
    10:00 - 11:00
     
    Complexity of the Graph Homomorphism Problem
    Philipp Niemietz
  • 24.03.2017
    10:15 - 11:45
     
    Parity games in quasi-polynomial time
    Katrin Dannert
    The problem of deciding parity games is known to be in NP and in co-NP but it is unknown, whether it is solvable in polynomial time. Recently it has been shown that the problem can be solved both in quasipolynomial time and in FPT with the number of colours as the parameter. In order to obtain these runtimes, space- efficient winning statistics for a play are maintained by building up and combining "favourable" sequences whose lengths are powers of two. This yields an alternating polylogarithmic space algorithm, which can be translated both into a quasipolyno- mial time algorithm and an FPT algorithm. Based on the paper Deciding Parity Games in Quasipolynomial Time by Calude, Jain, Khoussainov, Li and Stephan
  • 20.03.2017
    11:00 - 12:00
     
    Properties of Limit Deterministic Büchi Automata
    Max Ohn
  • 20.03.2017
    12:00 - 13:00
     
    Uniformization of Rational Relations
    Yordan Manolov
  • 14.03.2017
    11:00 - 12:00
     
    Logiken mit Multiteam-Semantik
    Richard Wilke
    Klassische Logiken werden mit der so genannten Tarski-Semantik aus- gewertet. Dabei gibt eine Zuweisung den vorkommenden Variablen einer Formel ihre Bedeutung. Dieses Konzept st ̈oßt an seine Grenzen sobald man Abh ̈angigkeiten zwischen den Variablen ausdru ̈cken m ̈ochte. Verschiedene Logiken sind entwickelt worden um derartige Aussagen treffen zu k ̈onnen. Das ju ̈ngste Konzept ist die Team-Semantik. Man betrachtet dort zu ei- ner Formel eine Menge von Zuweisungen, die miteinander interagieren. So kann man beispielsweise die Aussage treffen, dass der Wert einer Variable y ausschließlich vom Wert der Variable x abh ̈angig ist. Ein Team kann als Datenbank betrachtet werden, wobei jede Zuweisung einen Eintrag repr ̈asentiert. In reellen Anwendungen kann es von großer Be- deutung sein, wie oft ein gewisser Eintrag vorkommt. Wir betrachtet daher Logiken mit Multiteam-Semantik, welche sich eben dieser Herausforderung stellen.
  • 03.03.2017
    10:15 - 11:15
     
    The First-Order Logic of Hyperproperties
    Martin Zimmermann
    We investigate the logical foundations of hyperproperties. Hyperproperties generalize trace properties, which are sets of traces, to sets of sets of traces. The most prominent application of hyperproperties is information flow security: information flow policies characterize the secrecy and integrity of a system by comparing two or more execution traces, for example by comparing the observations made by an external observer on execution traces that result from different values of a secret variable. In this paper, we establish the first connection between temporal logics for hyperproperties and first-order logic. Kamp's seminal theorem (in the formulation due to Gabbay et al.) states that linear-time temporal logic (LTL) is expressively equivalent to first-order logic over the natural numbers with order. We introduce first-order logic over sets of traces and prove that HyperLTL, the extension of LTL to hyperproperties, is strictly subsumed by this logic. We furthermore exhibit a fragment that is expressively equivalent to HyperLTL, thereby establishing Kamp's theorem for hyperproperties. Based on joint work with Bernd Finkbeiner (Saarland University).
  • 03.03.2017
    10:15 - 11:15
     
    The First-Order Logic of Hyperproperties
    Martin Zimmermann
    We investigate the logical foundations of hyperproperties. Hyperproperties generalize trace properties, which are sets of traces, to sets of sets of traces. The most prominent application of hyperproperties is information flow security: information flow policies characterize the secrecy and integrity of a system by comparing two or more execution traces, for example by comparing the observations made by an external observer on execution traces that result from different values of a secret variable. In this paper, we establish the first connection between temporal logics for hyperproperties and first-order logic. Kamp's seminal theorem (in the formulation due to Gabbay et al.) states that linear-time temporal logic (LTL) is expressively equivalent to first-order logic over the natural numbers with order. We introduce first-order logic over sets of traces and prove that HyperLTL, the extension of LTL to hyperproperties, is strictly subsumed by this logic. We furthermore exhibit a fragment that is expressively equivalent to HyperLTL, thereby establishing Kamp's theorem for hyperproperties. Based on joint work with Bernd Finkbeiner (Saarland University).
  • 17.02.2017
    10:15 - 11:15
     
    Compact graphs and the LP approach to GI
    Gaurav Rattan
    Using the LP formulation for GI, we describe the class of compact graphs, proposed by Tinhofer. Isomorphism testing for such graphs can be done efficiently, using the linear program for GI. The recognition problem for such graphs remains open. Towards a partial understanding of this class, we describe some connections of this class with Color Refinement and Individualization techniques.
  • 03.02.2017
    10:15 - 11:15
    ATI
    An exponential lower bound for Individualization/Refinement algorithms for Graph Isomorphism
    Daniel Neuen
    The individualization and refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, it provides the only methods for isomorphism testing which are also viable for practical uses. From the theoretical point of view, no meaningful lower bounds on the worst case complexity of these tools are known. In fact, it is an open question whether these simple methods might provide similar upper bounds than existing algorithms combining complex group theoretic and combinatorial tools. In this work we give a negative answer to this question and construct a family of graphs that provides an exponential lower bound for methods based on the individualization and refinement paradigm. Other than previous constructions like Miyazaki graphs, our construction is immune to changing the cell selector or invariants used within the algorithm. Furthermore, our graphs also provide exponential lower bounds in the case where k-dimensional Weisfeiler Leman is used for refinement instead of color refinement (i.e. 1-dimensional Weisfeiler Leman) and the arguments even work when the automorphism group is initially known to the algorithm. In particular, under some moderate assumptions, our lower bounds are independent from which heuristics are used for cell selection, node invariants and automorphism detection.
  • 03.02.2017
    10:15 - 11:15
    ATI
    An exponential lower bound for Individualization/Refinement algorithms for Graph Isomorphism
    Daniel Neuen
    The individualization and refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, it provides the only methods for isomorphism testing which are also viable for practical uses. From the theoretical point of view, no meaningful lower bounds on the worst case complexity of these tools are known. In fact, it is an open question whether these simple methods might provide similar upper bounds than existing algorithms combining complex group theoretic and combinatorial tools. In this work we give a negative answer to this question and construct a family of graphs that provides an exponential lower bound for methods based on the individualization and refinement paradigm. Other than previous constructions like Miyazaki graphs, our construction is immune to changing the cell selector or invariants used within the algorithm. Furthermore, our graphs also provide exponential lower bounds in the case where k-dimensional Weisfeiler Leman is used for refinement instead of color refinement (i.e. 1-dimensional Weisfeiler Leman) and the arguments even work when the automorphism group is initially known to the algorithm. In particular, under some moderate assumptions, our lower bounds are independent from which heuristics are used for cell selection, node invariants and automorphism detection.
  • 27.01.2017
    10:15 - 11:15
    ATI
    N-Memory Automata Over the Alphabet N
    Patrick Landwehr
    An automaton model for words over the alphabet of the natural numbers is presented - the so called N-memory automaton. We explain its close connection to MSO-logic and discuss its expressive power and closure properties. Additionally we show among other decidability results the solvability of the non-emptiness problem.
  • 20.01.2017
    10:15 - 11:15
    ATI
    Ramanujan Graphs in Polynomial Time
    Lars Beckers