Talks

Showing 1 - 9 of 9 Results

  • Date
     
    Title
  • 20/11/2019
    13:15 - 13:45
    MSc
    Algorithms for Maximum Matching Width
    Yassin Bahloul
  • 20/11/2019
    15:00 - 15:30
    BSc
    The Fine-Grained Complexity of First-Order Properties
    Louis Härtel
    Based on the results by Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova and Ryan Williams, we break down the fine-grained complexity of first-order properties by analyzing their reduction from any model-checking problem on a (k + 1)-quantifier first-order formula to the sparse version of k-Orthogonal Vectors, and summarize their algorithmic improvements and consequences for common fine-grained conjectures.
  • 22/11/2019
    10:00 - 11:00
    ATI
    Ambiguity in Probabilistic Büchi Automata
    Anton Pirogov
    Probabilistic Büchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that goes beyond the regular languages. In this talk I will present new classes of restricted PBA which are still regular, strongly relying on notions concerning ambiguity in classical ω-automata.
  • 29/11/2019
    10:00 - 11:00
    ATI
    Fractional Sets, Fractional Decompositions, and Fractional Tangles
    Eva Fluck
  • 29/11/2019
    10:00 - 11:00
    ATI
    Fractional Sets, Fractional Decompositions, and Fractional Tangles
    Eva Fluck
  • 06/12/2019
    10:00 - 11:00
    ATI
  • 13/12/2019
    10:00 - 11:00
    ATI
  • 10/01/2020
    10:00 - 11:00
    ATI
  • 17/01/2020
    10:00 - 11:00
    ATI