
Termin
Titel

26.01.2018
10:15  11:15
ATI
SMTbased Flat Model Checking for LTL with Counting
Anton Pirogov

23.01.2018
10:00  11:00
Provenance for Logics with Team Semantics
Lukas Huwald
Master Kolloquium Abstract: Provenance analysis is a concept that originated in the field of database theory which unifies several nonstandard semantics for database queries, such as bag semantics or probabilistic semantics. These different semantics can be captured in an algebraic framework using various semirings, and are special instances of computations in a general provenance semiring. While the previous work on provenance semantics focused mainly on positive query languages for databases, Grädel and Tannen recently introduced provenance semantics for logical languages that also include negation, e.g. full first order logic. In this master thesis talk we introduce semiring semantics and provenance analysis for logics with team semantics, such as Väänänen's dependence logic. The main features of these logics are atomic formulae that allow reasoning about dependence and independence relations between variables. We define semiring semantics for these logics and analyze their properties, e.g. with respect to locality, closure properties and game theoretic semantics. We show that in the class of idempotent semirings, many of the known results for booolean semantics are preserved when considering semiring semantics. This is not the case for general semirings: many logics that are equivalent for boolean semantics can be separated for semiring semantics. In particular we show that independence logic and existential second order logic are incomparable for semiring semantics, but certain extensions of these logics remain equivalent.

19.01.2018
10:15  11:15
ATI
Theories of Automatic Structures within the Exponential Time Hierarchy
Peter Lindner

22.12.2017
10:15  11:15
ATI
Capacity of Neural Net works for Lifelong Learn ing of Composable Tasks
work by Leslie G. Valiant
Speaker: Dominik Meier

18.12.2017
10:00  10:30
Learning Algorithms for Sequential Transducers
Tom Biskup
Bachelor talk

15.12.2017
10:15  11:15
ATI
Learning Symbolic Automata
work by Samuel Drews and Loris D'Antoni
Speaker: Leo Krömker

08.12.2017
10:15  11:15
ATI
Set Similarity Search Beyond MinHash
work by Tobias Christiani, Rasmus Pagh
Speaker: Lukas Tiago Bolte

17.11.2017
10:15  11:15
ATI
Isomorphism of bounded degree graphs
Daniel Neuen
something with isomorphism and bounded degree

06.11.2017
14:00  15:00
The parameterized complexity of counting perfect matchings and other subgraphs
Radu Curticapean
Counting problems became a part of TCS at least since Valiant introduced the class #P and proved that counting perfect matchings is #Pcomplete. Polynomialtime algorithms for exact counting problems tend to be rare and curious, but even for the #Phard problems, some progress can be made through the usual relaxations studied in TCS. Among those, this talk will cover the parameterized complexity of counting problems, as introduced by Flum and Grohe, and independently by McCartin. One part of the talk will focus on the complexity of counting perfect matchings, a problem studied in algebra, combinatorics, and statistical physics. We discuss how this problem reacts to structural parameters from graph minor theory like the genus, the apex number and the Hadwiger number. This contains some algorithmic results, but also conditional lower bounds under the exponentialtime hypothesis ETH and its stronger sibling SETH. We also consider the problems of counting general subgraphs H in a host graph G, this time parameterized by the size of H. This gives rise to the problems #Sub(C) for fixed graph classes C: Given inputs H and G, where H is from C, count the Hcopies in G. We show a dichotomy theorem for these problems, together with recently found connections to a framework developed by Lovász. The talk is based on several works, some of which involved Holger Dell, Dániel Marx, and Mingji Xia.

03.11.2017
10:15  11:15

03.11.2017
10:15  11:15

27.10.2017
10:15  11:15
Uniformization Problems for Synchronizations of Relations on WordsSarah WinterA uniformization of a binary relation is a function that is contained in the relation and has the same domain as the relation. The synthesis problem asks for effective uniformization for classes of relations and functions that can be implemented in a specific way. We consider the synthesis problem for regular relations over finite words (also called automatic or synchronized rational relations) by functions implemented by specific classes of sequential transducers. It is known that the problem ``Given a regular relation, does it have a uniformization by a subsequential transducer?'' is decidable in the two variants where the uniformization can either be implemented by an arbitrary subsequential transducer or it has to be implemented by a synchronous transducer. We prove the decidability of a generalization of these two problems in which the allowed input/output behavior of the subsequential transducer is specified by a synchronization language.

27.10.2017
13:30  14:15
Preprocessing algorithms for the Graph Isomorphism Problem
Lorena Reintgen
We develop a new approach to solve the Graph Isomorphism Problem (GI) for input graphs G and H over the same vertex set V that are close with respect to permutation distance. We show that if the input pair of graphs have permutation distance at most k, then it is possible to construct in quadratic time an equivalent instance of size at most f(k), for a computable function f, and decide whether there exists an isomorphism from G to H. Our algorithm is thus a kernelization algorithm and can be used as a preprocessing step for inputs with low permutation distance. The algorithm consists of four steps. In the first step we find a relabeling on the vertices of the symmetric difference $G triangle H$ as to restrict the maximal degree within $G triangle H$. Next, we construct from the previous result (G',H) a subset of vertices that contains the set of vertices that have to be relabeled in order to identify G' with H. This result in turn is used to construct a smaller instance for Colored Graph Isomorphism. In the final step this colored instance is again transformed into an uncolored graph, which constitutes our kernel instance.

20.10.2017
10:00  11:00
Graph Similarity and Approximate IsomorphismGaurav RattanThe graph similarity problem, also known as approximate graph isomorphism or graph matching problem has been extensively studied in the machine learning community, but has not received much attention in the algorithms community. Given two graphs G,H with adjacency matrices A_G,A_H, a wellstudied measure of similarity is the Frobenius distance dist(G,H):=min_P  A_G^P  A_H _F, where P ranges over all permutations of the vertex set of G, A_G^P denotes the matrix obtained from A_G by permuting rows and columns according to P, and M_F is the Frobenius norm of a matrix M. The (weighted) graph similarity problem, denoted by SIM (WSIM), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NPhard even for severely restricted cases. It is known that SIM (WSIM) is NPhard: we strengthen this hardness result by showing that the problem remains NPhard even for the class of trees. Identifying the boundary of tractability for this problem is best done in the framework of linear algebra. Our main result is a polynomial time algorithm for the special case of WSIM where both input matrices are positive semidefinite, have boundedrank, and where one of the matrices has a bounded clustering number. The clustering number is a natural algorithmic parameter arising from spectral clustering techniques. We complement this result by showing NPhardness for matrices of bounded rank and for positivesemidefinite matrices.

06.10.2017
11:00  11:30
Learning Algorithms for Tree Automata
Patrick Smandzich
Master's thesis presentation

04.10.2017
14:00  15:00
A PolynomialTime Randomized Reduction from Tournament Isomorphism to Tournament AsymmetryPascal SchweitzerThe paper develops a new technique to extract a characteristic subset from a random source that repeatedly samples from a set of elements. Here a characteristic subset is a set that when containing an element contains all elements that have the same probability. With this technique at hand the paper looks at the special case of the tournament isomorphism problem that stands in the way towards a polynomialtime algorithm for the graph isomorphism problem. Noting that there is a reduction from the automorphism (asymmetry) problem to the isomorphism problem, a reduction in the other direction is nevertheless not known and remains a thorny open problem. Applying the new technique, we develop a randomized polynomialtime Turingreduction from the tournament isomorphism problem to the tournament automorphism problem. This is the first such reduction for any kind of combinatorial object not known to have a polynomialtime solvable isomorphism problem

29.09.2017
10:00  10:30
Anfragebearbeitung mit konstanter Verzögerung
Mario Jörres
Das Kolloquium gibt einen Überblick über einige Ergebnisse bezüglich der Bearbeitung von Datenbankanfragen. Dabei beschränken wir uns auf die Klasse der konjunktiven Anfragen, da eine Reihe von bekannten NPvollständigen Problemen als solche ausgedrückt werden kann, und stellen eine alternative Betrachtungsweise für die Komplexität des Auswertungsproblems solcher Anfragen vor. Wir nehmen an, es sei nicht notwendig, alle Antworten auf eine Anfrage zugleich zu erhalten, sondern es genügt, diese mit konstanter Verzögerung zwischen zwei aufeinanderfolgenden Antworten auszugeben, nachdem eine Vorverarbeitung in linearer Zeit stattfand. Dann kann man die Komplexität des Aufzählungsproblems anhand der Dauer der Vorverarbeitung und der Verzögerung betrachten.

29.09.2017
10:45  11:15
Algorithmic aspects of pfaffian orientations
Laurids Vollmann
In this thesis we will examine the current research concerning the calculation of pfaffian orientations on different classes of graphs. Pfaffian orientations assign a direction to each edge in an undirected graph in a specific way and allow us to efficently calculate the amount of perfect matchings. Not every graph has a pfaffian orientation and for most graphs finding one is hard. We will also briefly present some polynomialtime equivalent problems.

29.09.2017
11:30  12:00
Hashing Techniques for Computing Frequency Moments (Bachelor, Deutscher Vortrag)
Yannick Epstein
Randomized hashing is a fundamental part of approximating frequency mo ments of data streams. To approximate the second frequency moment of a data stream, a strongly 4universal family of hash functions is mandatory to give strong guarantees of the returned estimation’s accuracy. When implementing these approximation algo rithms, arguments against using a strongly 4universal family of hash functions are the need for shorter runtime or only having access to few random bits. We evaluate ex perimentally the effects of using different hashing schemes to approximate the second frequency moment of real data streams. We obtain that universal, strongly 2universal hashing, and a strongly 3universal tabulation hashing scheme break the algorithms. However two randomized hash functions without theoretical guarantees seem to work as well as strongly 4universal hashing.

29.09.2017
12:15  12:45
Lower Bounds for Parallel Query Processing
Joshua Fürste
Conjunctive queries represent an important subset of queries issued on relational databases. We study the problem of computing conjunctive queries over large distributed databases. Using the structures of a query Q and the skew in the data, we take a look at the amount of communication required over one or multiple communication rounds, that is required to compute Q.

29.09.2017
10:00  10:30
Anfragebearbeitung mit konstanter Verzögerung
Mario Jörres
Das Kolloquium gibt einen Überblick über einige Ergebnisse bezüglich der Bearbeitung von Datenbankanfragen. Dabei beschränken wir uns auf die Klasse der konjunktiven Anfragen, da eine Reihe von bekannten NPvollständigen Problemen als solche ausgedrückt werden kann, und stellen eine alternative Betrachtungsweise für die Komplexität des Auswertungsproblems solcher Anfragen vor. Wir nehmen an, es sei nicht notwendig, alle Antworten auf eine Anfrage zugleich zu erhalten, sondern es genügt, diese mit konstanter Verzögerung zwischen zwei aufeinanderfolgenden Antworten auszugeben, nachdem eine Vorverarbeitung in linearer Zeit stattfand. Dann kann man die Komplexität des Aufzählungsproblems anhand der Dauer der Vorverarbeitung und der Verzögerung betrachten.

29.09.2017
10:45  11:15
Algorithmic aspects of pfaffian orientations
Laurids Vollmann
In this thesis we will examine the current research concerning the calculation of pfaffian orientations on different classes of graphs. Pfaffian orientations assign a direction to each edge in an undirected graph in a specific way and allow us to efficently calculate the amount of perfect matchings. Not every graph has a pfaffian orientation and for most graphs finding one is hard. We will also briefly present some polynomialtime equivalent problems.

29.09.2017
11:30  12:00
Hashing Techniques for Computing Frequency Moments (Bachelor, Deutscher Vortrag)
Yannick Epstein
Randomized hashing is a fundamental part of approximating frequency mo ments of data streams. To approximate the second frequency moment of a data stream, a strongly 4universal family of hash functions is mandatory to give strong guarantees of the returned estimation’s accuracy. When implementing these approximation algo rithms, arguments against using a strongly 4universal family of hash functions are the need for shorter runtime or only having access to few random bits. We evaluate ex perimentally the effects of using different hashing schemes to approximate the second frequency moment of real data streams. We obtain that universal, strongly 2universal hashing, and a strongly 3universal tabulation hashing scheme break the algorithms. However two randomized hash functions without theoretical guarantees seem to work as well as strongly 4universal hashing.

29.09.2017
12:15  12:45
Lower Bounds for Parallel Query Processing
Joshua Fürste
Conjunctive queries represent an important subset of queries issued on relational databases. We study the problem of computing conjunctive queries over large distributed databases. Using the structures of a query Q and the skew in the data, we take a look at the amount of communication required over one or multiple communication rounds, that is required to compute Q.

28.09.2017
11:00  12:00
A comparison of algorithms for games on pushdown automata and contextfree games
Michael Mutert
Bachelor Kolloquium

28.09.2017
11:00  12:00
A comparison of algorithms for games on pushdown automata and contextfree games
Michael Mutert
Bachelor Kolloquium

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

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 LowenheimSkolem property
Abhisekh Sankaran
We present a modeltheoretic property of finite structures, that can be seen to be a finitary analogue of the wellstudied downward LowenheimSkolem 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 treedepth, those of bounded shrubdepth and mpartite cographs. Further, EBSP remains preserved in the classes generated from the above using various wellstudied operations, such as complementation, transpose, the linegraph 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 selfsimilarity 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 FOInterpretations
Dimitri Rusin

01.09.2017
10:00  11:00
FO Model Checking on some Dense Graph Classes using FOInterpretations
Dimitri Rusin

31.08.2017
12:00  12:30
Definierbarkeit abelscher Summationsprobleme in Fixpunktlogiken und TCLogiken
Yannic Rohde

31.08.2017
12:00  12:30
Definierbarkeit abelscher Summationsprobleme in Fixpunktlogiken und TCLogiken
Yannic Rohde

30.08.2017
11:00  12:00
Homomorphisms are a good basis for counting small subgraphsHolger DellWe introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constantsize induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of Hcopies (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 kedge matchings or O(n0.46k+c) time for kcycles. 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 vertexcolored graphs H and G, where H is from a fixed class H, we want to count colorpreserving Hcopies in G. We show that this problem is either polynomialtime 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 subgraphsHolger DellWe introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constantsize induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of Hcopies (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 kedge matchings or O(n0.46k+c) time for kcycles. 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 vertexcolored graphs H and G, where H is from a fixed class H, we want to count colorpreserving Hcopies in G. We show that this problem is either polynomialtime 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 Lcomplete) by Datta, Limaye, Nimbhorkar, Thierauf and Wagner. We generalize the decomposition technique used in their result to work with minorclosed graph classes whose 3connected members fulfill a fixability condition and admit a logspace canonization algorithm.

24.08.2017
10:30  10:30
WeisfeilerLehman 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 WeisfeilerLehman 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 stateoftheart 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 WeisfeilerLehman subtree kernel. Before we make these observations we provide brief introductions into WeisfeilerLehman 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 bottomup recursion upon these components. For this to work I introduce a generalization of the fixing number, the socalled vertexarc 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 minorclosed graph class that allows isomorphism testing and computing the vertexarc fixing number of its triconnected graphs in polynomial time.

28.07.2017
10:15  11:45
ATI
FixedParameter Tractable Canonization for Graphs of Bounded TreewidthDaniel 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 twoway 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 BeyondChristopher MorrisGraph kernels are a popular approach to graph comparison and at the heart of many machine learning applications in bioinformatics, imaging, and socialnetwork 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 WeisfeilerLehman 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 boundeddegree 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 algorithmsSpyros AngelopoulosStochastic 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 twofold. 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 kserver 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 TimeSpace Lower Bound for Parity Learning
work by Ran Raz

07.07.2017
11:15  12:15
Enumerating Tree Decompositions: Why and HowBenny KimelfeldMany 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 subproblems 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 highquality tree decompositions for the application to choose from. I will describe our application of tree decompositions in the context of “worstcase optimal” joins  a new breed of inmemory 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, coauthored with Nofar Carmeli, Yoav Etsion, Oren Kalinsky and Batya Kenig.

04.07.2017
16:00  17:00
The hardness of embedding grids and wallsYijia ChenThe 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 fixedparameter 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 degreeIsolde AdlerProperty 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 firstorder logic is testable with a constant number of queries in constant time. On structures of bounded treewidth, monadic secondorder logic can be tested with a constant number of queries in polylogarithmic time. This is joint work with Frederik Harwath.