Termine Vorträge (Archiv)

Treffer 51 - 100 von 130 Ergebnissen

  • Termin
     
    Titel
  • 26.01.2018
    10:15 - 11:15
    ATI
    SMT-based 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 #P-complete. Polynomial-time algorithms for exact counting problems tend to be rare and curious, but even for the #P-hard 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 exponential-time 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 H-copies 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
     
    Isomorphism of Hypergraphs and Relational Structures
    Daniel Wiebking
  • 03.11.2017
    10:15 - 11:15
     
    Isomorphism of Hypergraphs and Relational Structures
    Daniel Wiebking
  • 27.10.2017
    10:15 - 11:15
     
    Uniformization Problems for Synchronizations of Relations on Words
    Sarah Winter
    A 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 Isomorphism
    Gaurav Rattan
    The 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 well-studied 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 NP-hard even for severely restricted cases. It is known that SIM (WSIM) is NP-hard: we strengthen this hardness result by showing that the problem remains NP-hard 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 semi-definite, have bounded-rank, 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 NP-hardness for matrices of bounded rank and for positive-semidefinite 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 Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry
    Pascal Schweitzer
    The 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 polynomial-time 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 polynomial-time Turing-reduction 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 polynomial-time 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 NP-vollstä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 polynomial-time 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 4-universal 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 4-universal 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 2-universal hashing, and a strongly 3-universal tabulation hashing scheme break the algorithms. However two randomized hash functions without theoretical guarantees seem to work as well as strongly 4-universal 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 NP-vollstä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 polynomial-time 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 4-universal 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 4-universal 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 2-universal hashing, and a strongly 3-universal tabulation hashing scheme break the algorithms. However two randomized hash functions without theoretical guarantees seem to work as well as strongly 4-universal 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 context-free games
    Michael Mutert
    Bachelor Kolloquium
  • 28.09.2017
    11:00 - 12:00
     
    A comparison of algorithms for games on pushdown automata and context-free 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 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.