Termine Vorträge (Archiv)

Treffer 1 - 50 von 194 Ergebnissen

  • Termin
     
    Titel
  • 09.09.2021
    11:00 - 11:30
    MSc
    Nondeterministic Deep Weisfeiler Leman
    Louis Härtel
    https://rwth.zoom.us/j/5419503919?pwd=enlnbm1mclNBNkVQZTgvVXR4RTRHZz09
  • 06.09.2021
    14:00 - 15:00
    BSc
    Bachelor-Kolloquium Matthäus Micun
    Counting and Sampling based on Nondeterministic Logspace Transducers Abstract: Transducers are Turing machines that, instead of deciding problems, compute witnesses. Additionally, non-deterministic Transducers compute relations of witnesses. In this paper, we discuss non-deterministic logspace transducers (NL transducers), as well as their unambiguous version (UL transducers). More specifically, we prove that for any relation computed by an NL transducer, we can enumerate the witnesses of a given word w with polynomial delay, count the number of all witnesses using a fully polynomial randomized approximation scheme (FPRAS), and uniformly generate a witness using a pre-processing polynomial time Las Vegas uniform generator (PPLVUG). Additionally, we connect these properties to non-deterministic finite automata, and prove that the #NFA problem admits an FPRAS.
  • 02.09.2021
    15:00 - 16:00
     
    Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs, Daniel Neuen
    Abstract: Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. In this talk I discuss a framework for obtaining n^{O(sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an n^{O(sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{O(sqrt{k} polylog(k))}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain such (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set.
  • 02.09.2021
    15:00 - 16:00
     
    Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs, Daniel Neuen
    Abstract: Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. In this talk I discuss a framework for obtaining n^{O(sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an n^{O(sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{O(sqrt{k} polylog(k))}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain such (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set.
  • 11.08.2021
    15:00 - 15:30
     
    Facility Location and Clustering on Planar and Almost Planar Graphs
    Sebastian Schaub
    Masterkolloquium


    Zoom-Meeting beitreten
    https://rwth.zoom.us/j/99375584947?pwd=UVNSaTBNRm1qL2ZneDExWVVZUUxKZz09
    Meeting-ID: 993 7558 4947
    Kenncode: 600407


    Abstract: In this thesis we will reflect the current state of research for the uniform facility location problem and k-Clustering in terms of approximability. We will focus our attention on the special case of the planar graph metric, because for the problems with general metric no polynomial-time approximation scheme exist.
    To illustrate this we will depict and explain four recent results which use different techniques for the analysis of the algorithms, including Voronoi Diagrams, r-divisions and coresets. The first result is an algorithm accuracy analysis for the uniform facility location, where we show that a commonly known local search algorithm is a polynomial-time approximation scheme. The second result is an efficient polynomial-time randomised approximation scheme, where we use an algorithm for the k-Median problem as a subroutine to derive a solution. For the third result we have another polynomial-time approximation scheme with a local search algorithm for the k-Clustering problems k-Median and k-Means. And the fourth result is a fully polynomial-time randomised approximation scheme for the k-Median problem, where the algorithm is based on constructing coresets.
  • 29.07.2021
    11:00 - 12:00
     
    Simulation Relations for Symbolic Automata, Rober Funk, Masterkolloquium
  • 29.07.2021
    11:00 - 12:00
     
    Simulation Relations for Symbolic Automata, Rober Funk, Masterkolloquium
  • 21.07.2021
    10:00 - 11:00
     
    Learning and Minimization of omega-Automata in the Presence of Don’t CareWords, Max Stachon
    Masterkollquium

    https://rwth.zoom.us/j/93883134873?pwd=Y1lKYXpEZHBlaHlmUWtHSG9VQ1M5Zz09

  • 14.07.2021
    10:00 - 12:00
     
    Tree Automata with Constraints on Infinite Trees
    Patrick Landwehr
  • 06.07.2021
    10:30 - 11:15
     
    Comparing Algorithms for Weak Parity Games, Jonas Förster

    Bachelorkolloquium

    https://rwth.zoom.us/j/94010226440?pwd=VnNFZzczR0p1ZUxNY2lLQnU2SmUxdz09

  • 28.06.2021
    12:30 - 13:30
    BSc
    The Logical Expressiveness of Graph Neural Networks
    Attila Lischka
    https://rwth.zoom.us/j/95314638975?pwd=bForQjRoZXN1YlhRd29IQlFVQkNuQT09
  • 28.06.2021
    12:30 - 13:30
    BSc
    The Logical Expressiveness of Graph Neural Networks
    Attila Lischka
    https://rwth.zoom.us/j/95314638975?pwd=bForQjRoZXN1YlhRd29IQlFVQkNuQT09
  • 14.06.2021
    16:00 - 16:30
     
    A Decomposition-Compatible Canonization Framework for the Graph Isomorphism Problem
    Daniel Wiebking
    https://rwth.zoom.us/j/94470149252?pwd=ZnYwVXQrbStveVdDNDk1V1BlN1lJUT09
  • 11.05.2021
    15:00 - 15:30
     
    Bachelorkolloquium Martin Krüßel
  • 16.04.2021
    14:00 - 14:30
     
    Bachelorkolloquium Jonas Groven
  • 22.03.2021
    10:30 - 11:15
     
    Bachelorkolloquium Jonathan Schneider
  • 01.03.2021
    10:00 - 10:45
     
    Bachelorvortrag Alexander Cushicondor
    Title: "Homomorphism Indistinguishability over Structures of Bounded Tree Depth" Abstract: It will be proved that two structures G, G' satisfy the same sentences of quantier rank at most k of first order logic with counting, if and only if they are homomorphism-indistinguishable over the class of structures of tree depth at most k.
  • 22.02.2021
    10:00 - 10:30
     
    Nondeterministic Automata with XOR-acceptance
    Jagadish Singh
    https://rwth.zoom.us/j/94253016445?pwd=VVdScGUzOFNJamZ5MCtRclYwK2xDdz09
  • 18.02.2021
    10:15 - 11:15
     
    Oberseminar Anton Pirogov: Determinization and Ambiguity of Classical and Probabilistic Büchi Automata
    Anton Pirogov

    Büchi automata can be seen as a straight-forward generalization of
    ordinary NFA,
    adapted to handle infinite words. While they were originally introduced for
    applications in decidability of logics, they became a popular tool for
    practical
    applications, e.g. in automata-based approaches to model checking and
    synthesis
    problems. Being arguably both the simplest and most well-known variant
    in the
    zoo of so-called omega-automata that are considered in this setting, they
    serve as an intermediate representation of omega-regular specifications of
    verification or synthesis requirements that are usually expressed in a more
    declarative fashion, e.g. using linear temporal logic.

    Unfortunately, nondeterministic automata are not directly suitable for
    certain
    applications, whereas deterministic Büchi automata are less expressive. This
    problem is usually solved by either constructing deterministic automata of a
    different kind, or by restricting their ambiguity, i.e., the maximal
    number of
    accepting runs on some word. In both cases, the transformation is expensive,
    yielding an exponential blow-up of the state space in the worst case.
    Therefore,
    optimized constructions and heuristics for common special cases are
    useful and
    in demand for actual practical applications.

    In this talk we present a new general construction for determinization from
    nondeterministic Büchi to deterministic parity automata that unifies the
    dominant branches of previous approaches based on the Safra construction
    and the
    Muller-Schupp construction. Additionally, we sketch a number of new
    heuristics
    for determinization, some of which exploit properties of our unified
    construction.

    Apart from the classical nondeterministic and deterministic variants of
    automata, it is natural to consider probabilistic automata, i.e.,
    automata that
    use a probability distribution on the states instead of nondeterminism
    to decide
    which state to go to next. It is known that in general, such automata
    are more
    expressive than classical automata and many decision problems are
    undecidable.
    We present subclasses of probabilistic automata that correspond to certain
    ambiguity classes and are not more expressive than classical automata.
  • 08.01.2021
    10:00 - 11:00
    ATI
    Deep Weisfeiler Leman
    Daniel Wiebking
    We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm.

    We prove that, as an abstract computational model, polynomial-time DeepWL-algorithms have exactly the same expressiveness as the logic Choiceless Polynomial Time (with counting) introduced by Blass, Gurevich, and Shelah (Ann. Pure Appl. Logic., 1999).

    It is a well-known open question whether the existence of a polynomial-time graph isomorphism test implies the existence of a polynomial-time canonisation algorithm. Our main technical result states that for each class of graphs (satisfying some mild closure condition), if there is a polynomial-time DeepWL isomorphism test, then there is a polynomial-time canonisation algorithm for this class. This implies that there is also a logic capturing polynomial time on this class.
  • 18.12.2020
    10:30 - 11:00
     
    Bachelor-Vortrag: The Logical Structure of Probabilistic Databases
    Jonas Lindner
    As probabilistic databases (PDBs) may be very large, compact representation systems for these frameworks have been studied. But because complete representation systems (like pc-tables) can lead to very complex probability spaces, considering simpler and more intuitive non-complete representation systems, e.g. TI-tables or BID-tables, is of interest. These fundamental ’building blocks’ are especially interesting as they can be extended with views from the relational calculus to be more expressive. Similar to work done by Das Sarma et al. on representation systems for incomplete databases, this thesis introduces logical properties in order to separate the classes of PDBs that are representable with non-complete representation systems. The properties studied take a PDB’s underlying incomplete database as well as its probability distribu- tion into account and therefore help to grasp its logical structure. Having conducted this examination, convex combinations of probabilistic databases are studied, as they offer some advantages over the commonly considered representation systems regarding expressiveness.
  • 12.11.2020
    11:00 - 11:30
     
    Connectivity and Routing using Graph Neural Networks
    Frorian Frantzen
    Graph Neural Networks form a deep learning architecture for machine learning tasks on graphs. Recently, they have been used to obtain heuristics for hard combinatorial problems such as TSP, SAT, or constraint satisfaction problems. The purpose of this thesis is to investigate how such approaches perform on computationally much easier shortest path problems. We will present lower bounds regarding the depth and width of a message passing neural network, which must be fulfilled for such a model to learn the shortest path problem. Then we will evaluate an existing neural network -- originally designed for the traveling salesperson problem -- for its applicability to the shortest path problem. While this network will fail with insignificant accuracies, these tests will allow us to derive unique challenges of the shortest path problem and which weaknesses in the architecture we need to fix to achieve better results. Based on these results, we will built our own neural network architecture and train it both supervised and unsupervised. We will evaluate this network in terms accuracy, scalability to larger graphs and how well the network generalizes the shortest path problem.
  • 30.10.2020
    10:00 - 11:00
    ATI
    Flag Algebras in Graph Theory
    Tim Seppelt
    Flag algebras as introduced by Razborov represent a powerful tool in extremal combinatorics. This talk will provide a gentle introduction to the framework highlighting applications graph theory. Moreover, limitations of flag algebraic techniques are discussed following the work of Hatami and Norine.
  • 30.10.2020
    10:00 - 11:00
    ATI
    Flag Algebras in Graph Theory
    Tim Seppelt
    Flag algebras as introduced by Razborov represent a powerful tool in extremal combinatorics. This talk will provide a gentle introduction to the framework highlighting applications graph theory. Moreover, limitations of flag algebraic techniques are discussed following the work of Hatami and Norine.
  • 27.10.2020
    14:00 - 14:30
    BSc
    The Fine-Grained Complexity of Longest Common Subsequence
    Benjamin Stutte
    [bachelor]We will examine approaches to fine-grained analyses of the Longest Common Subsequence (LCS) problem with special attention to recent results that have proven lower bounds for solving LCS under the Strong Exponential Time Hypothesis. We will first showcase two results, one by Abboud et al. (FOCS’15) and the other by Bringmann et al. (FOCS’15), where sub-quadratic lower bounds have been proven for the general LCS problem. Later, we turn to Bringmann et al.’s (SODA’18) which examined the optimal running time of multivariate LCS which proved lower bounds that coincide with the running times of the fastest known algorithms.
  • 27.10.2020
    14:45 - 15:15
    BSc
    Stable and Efficient Algorithms for Logarithmically Counting Homomorphisms from Selected Graph Classes
    Anton Florey
    Graph homomorphisms are mappings between two graphs H and G that preserve all edge relationsof the left-hand side graph. The graph homomorphism counting problem #Hom(H, G) asks for
    the number of homomorphisms from one graph H ∈ H to another graph G ∈ G. It is polynomial
    time solvable for certain left-hand graph classes H. As part of his recent master thesis, Maximilian
    Merz already provided implementations of various homomorphism counting algorithms. Unfor-
    tunately, they quickly get impracticable for large problem instances, as homomorphism numbers
    grow extremely fast. This work revisits most of these algorithms with the novel idea of counting
    the logarithm of these numbers. One main contribution is the implementation and evaluation of
    these adapted algorithms. For most of the newly implemented functions, a significant improve-
    ment in efficiency over the exact counting implementations can be measured. Further experiments
    also show that errors of this logarithmic approximation stay sufficiently close to the unavoidable

    accuracy loss induced by finite machine precision.
    https://rwth.zoom.us/j/95988725888?pwd=NUlaM05VdU5Kdkp0NXVTZHplWlFSQT09
  • 27.10.2020
    14:00 - 14:30
    BSc
    The Fine-Grained Complexity of Longest Common Subsequence
    Benjamin Stutte
    [bachelor]We will examine approaches to fine-grained analyses of the Longest Common Subsequence (LCS) problem with special attention to recent results that have proven lower bounds for solving LCS under the Strong Exponential Time Hypothesis. We will first showcase two results, one by Abboud et al. (FOCS’15) and the other by Bringmann et al. (FOCS’15), where sub-quadratic lower bounds have been proven for the general LCS problem. Later, we turn to Bringmann et al.’s (SODA’18) which examined the optimal running time of multivariate LCS which proved lower bounds that coincide with the running times of the fastest known algorithms.
  • 27.10.2020
    14:45 - 15:15
    BSc
    Stable and Efficient Algorithms for Logarithmically Counting Homomorphisms from Selected Graph Classes
    Anton Florey
    Graph homomorphisms are mappings between two graphs H and G that preserve all edge relationsof the left-hand side graph. The graph homomorphism counting problem #Hom(H, G) asks for
    the number of homomorphisms from one graph H ∈ H to another graph G ∈ G. It is polynomial
    time solvable for certain left-hand graph classes H. As part of his recent master thesis, Maximilian
    Merz already provided implementations of various homomorphism counting algorithms. Unfor-
    tunately, they quickly get impracticable for large problem instances, as homomorphism numbers
    grow extremely fast. This work revisits most of these algorithms with the novel idea of counting
    the logarithm of these numbers. One main contribution is the implementation and evaluation of
    these adapted algorithms. For most of the newly implemented functions, a significant improve-
    ment in efficiency over the exact counting implementations can be measured. Further experiments
    also show that errors of this logarithmic approximation stay sufficiently close to the unavoidable

    accuracy loss induced by finite machine precision.
    https://rwth.zoom.us/j/95988725888?pwd=NUlaM05VdU5Kdkp0NXVTZHplWlFSQT09
  • 23.10.2020
    10:30 - 11:00
    MSc
    Detecting Substructures with Graph Neural Networks
    Michael Scholkemper
    [master]We present theoretical results relating the computational expressiveness of graph neural networks (GNNs) to the color refinement algorithm for graph isomorphism (Morris et al., X et al.). These yield that given the wrong initialisation, graph neural networks are not able to detect triangles on regular graphs. We introduce a refinement algorithm for graph isomorphism that outperforms color refinement on regular graphs and propose a GNN-architecture motivated by this new algorithm. We experimentally investigate the effect of different initialisations on  the detection of triangles and extend this to k-cycles and k-cliques.
  • 16.10.2020
    10:00 - 11:00
    ATI
    Learning Concepts Described by Weight Aggregation Logic
    Steffen van Bergerem
    We consider weighted structures, which extend ordinary relational structures by assigning weights, i.e. elements from a particular group or ring, to tuples present in the structure. We introduce an extension of first-order logic that allows to aggregate weights of tuples, compare such aggregates, and use them to build more complex formulas. We provide locality properties of fragments of this logic including Feferman-Vaught decompositions and a Gaifman normal form for a fragment called FOW1, as well as a localisation theorem for a larger fragment called FOWA1. This fragment can express concepts from various machine learning scenarios. Using the locality properties, we show that concepts definable in FOWA1 over a weighted background structure of at most polylogarithmic degree are agnostically PAC-learnable in polylogarithmic time after pseudo-linear time preprocessing. This is joint work with Nicole Schweikardt.
  • 13.10.2020
    10:00 - 10:30
    BSc
    A comparison of translation from LTL to Büchi automata
    Anna Maiworm
  • 01.10.2020
    10:00 - 10:45
     
    Bachelor Vortrag Jan-Christoph Kassing
    Vortrag zur Bachelorarbeit: The Recursive Algorithm for Parity Games
  • 01.10.2020
    10:00 - 10:45
     
    Bachelor Vortrag Jan-Christoph Kassing
    Vortrag zur Bachelorarbeit: The Recursive Algorithm for Parity Games
  • 29.09.2020
    10:00 - 10:45
     
    Bachelor-Vortrag Johannes Lehmann
    Vortrag zur Bachelorarbeit "Exact Minimization of omega-Automata"
  • 29.09.2020
    10:00 - 10:45
     
    Bachelor-Vortrag Johannes Lehmann
    Vortrag zur Bachelorarbeit "Exact Minimization of omega-Automata"
  • 25.09.2020
    10:30 - 11:00
    MSc
    Master-Vortrag: Graph Autoencoder for Chemical Compounds
    Stefanie Winkler
    https://rwth.zoom.us/j/91919735145?pwd=OWFJMDZ5aTErUjhLWEN0T1AwY0lIdz09 A challenging task in fuel design is to find suitable molecules that optimise desired properties like cetane and octane numbers. Our goal is to automate the generation of molecular graphs whose corresponding molecules serve as components for fuels with a high auto-ignition quality. We use three different neural network models built on variational autoencoders and a generative adversarial network: JT-VAE by Jin et al., MHG-VAE by Kajino and MolGAN by De Cao and Kipf [1–3]. Using a subset of QM9 for training, we adapt the models to optimise different combinations of the cetane and octane numbers of new molecules through Bayesian optimisation. Our results show that all models are able to produce valid molecules with high cetane and octane numbers. MHG-VAE is able to generate most of the highest scoring molecules in the different experiments. Moreover, it creates a lot more unique molecules than the other two models, many of which are easy to synthesise.
  • 25.09.2020
    11:15 - 12:00
    BSc
    Lower Bounds for the Weisfeiler-Leman Dimension of Graphs of Bounded Tree Width
    Lea Schirp
    The Weisfeiler-Leman (WL) algorithm is an iterative approach used to classify graphs and other relational structures. For every natural number k, there is a k-dimensional version, which colors k-tuples of vertices, running in polynomial time but there are also non-isomorphic graphs, which the k-dim version cannot distinguish. This makes it useful to know the WL-dimension of a graph, which is the least natural number k such that the k-dim WL distinguishes the graph from all other non-isomorphic graphs. It is known that bounds on the WL dimension of a graph can be determined if its tree width is known. In this talk, we present tools for computing the tree width of a graph with a focus on Tamaki's implementation. We finally discuss the results of an experimental evaluation of the tree width of these graphs with the goal of finding out if the currently best known bounds on the WL dimension of graphs parametrized by their tree width are tight.
  • 25.09.2020
    12:30 - 13:00
    BSc
    Counting Homomorphisms via Model Counting and Knowledge Compilation
    Patrick Bögel
    The homomorphism counting problem #HOM asks how many homomorphisms there are from a graph H to a graph G. The model counting problem #SAT asks how many satisfying assignments a propositional formula has. Both problems are #P-complete, but #HOM becomes tractable if the left-hand side graphs are restricted to a class of bounded tree-width. In this talk we consider reductions from #HOM to #SAT with special attention to whether the tractable subproblems of #HOM are mapped to tractable subproblems of #SAT. Specifically we find reductions that map homomorphism counting instances where the left-hand side graph is a tree, to formulas which adhere to structural restrictions under which #SAT becomes tractable. We also utilize the approach of knowledge compilation to create formulas in a representation that allows for the model count to be calculated in linear time of its size. We evaluate the reductions practically with multiple state-of-the-art model counters and find the reduction to be inferior to the direct approach.
  • 18.09.2020
    10:00 - 11:00
    ATI
    Tuple-Independent Representations of Probabilistic Databases
    Christoph Standke
    https://rwth.zoom.us/j/96525649453?pwd=bHRma0lmV2xuRTNhWUdQbi9ockdNZz09
  • 03.08.2020
    12:00 - 12:30
    BSc
    Bachelor Kolloquium Meder
  • 28.07.2020
    16:00 - 17:00
     
    Vortrag Wolfgang Gatterbauer
  • 28.07.2020
    16:00 - 17:00
     
    Vortrag Wolfgang Gatterbauer
  • 26.06.2020
    10:00 - 11:00
    ATI
    ATI Seminar Jan Böker
    Jan Böker
  • 19.06.2020
    10:00 - 10:45
    ATI
    ATI Seminar Vortrag Steffen van Bergerem
    Steffen van Bergerem
  • 05.06.2020
    10:00 - 11:00
    ATI
    omega-Word Automata with Global Constraints
    Patrick Landwehr
  • 29.05.2020
    10:00 - 10:30
    ATI
    Graph isomorphism in quasipolynomial time parameterized by treewidth
    Daniel Wiebking
  • 22.05.2020
    10:00 - 11:00
    ATI
    The Iteration Number of Colour Refinement
    Sandra Kiefer
    The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n-1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes |G|-1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n ≥ 10, there are graphs on n vertices on which Colour Refinement requires at least n-2 iterations to reach stabilisation. This is joint work with Brendan McKay.
  • 27.02.2020
    10:00 - 10:30
    MSc
    Unsupervised machine learning for constraint satisfaction problems
    Jan Tönshoff
  • 27.02.2020
    10:00 - 10:30
    MSc
    Unsupervised machine learning for constraint satisfaction problems
    Jan Tönshoff
  • 17.01.2020
    10:00 - 11:00
    ATI
    Generative Datalog with Continuous Distributions
    Peter Lindner
    Probabilistic Databases (PDBs) are a formal model of uncertainty in relational databases, as might occur in a variety of practical application scenarios such as noisy or unreliable input data, data integration or data cleaning. Quite recently, Bárány et al. (TODS 2017) proposed a language called "Probabilistic Programming Datalog (PPDL)" which uses classic Datalog rules that are extended by random sampling. In a nutshell, PPDL is a declarative probabilistic programming language with very close ties to database applications and can be seen as a tool to specify PDBs. In this talk, we focus on the generative part of the language, "Generative Datalog". While the original language of Bárány et al. only supported discrete probability distributions, we allow using probability density functions and inputs that are already PDBs themselves. We present the formal semantics of the language and discuss various properties and consequences, most notably, the support of PDB inputs and robustness with respect to the order of rule applications. This is joint work with M. Grohe, B. L. Kaminski, J.-P. Katoen.