Organizatorzy

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

11 października 2017 14:15
Bartek Klin (Uniwersytet Warszawski)
mu-calculus with atoms
True to the spirit of "\lambda x. (x with atoms)", I will present a modal mu-calculus with atoms. I will also explain what is wrong with it, and how it could perhaps be improved. This …
4 października 2017 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
First-order list functions (joint work with Laure Daviaud and Krishna S)
We define a class of functions, called first-order list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pairs of lists, etc. The definition is in the style of …
7 czerwca 2017 14:15
Sylvain Schmitz (ENS de Cachan)
Downward-closures and PTL separability (second part)
I'll present an approach to computing downward-closures and solving separability by piecewise-testable sets using ideal decompositions. The talk will be based on a joint paper with J. Goubault-Larrecq published at ICALP last year.
31 maja 2017 14:15
Thomas Zeume (Uniwersytet Warszawski)
Lower bounds in Dynamic Complexity
Unconditional lower bounds are are hard to prove. For this reason recent work on inexpressibility for dynamic complexity has been centered around fragments of DynFO (i.e. the class of queries maintainable using first-order formulas). In …
24 maja 2017 14:15
Sylvain Schmitz (ENS de Cachan)
Downward-closures and PTL separability
I'll present an approach to computing downward-closures and solving separability by piecewise-testable sets using ideal decompositions. The talk will be based on a joint paper with J. Goubault-Larrecq published at ICALP last year.
17 maja 2017 14:15
Bartek Klin (Uniwersytet Warszawski)
Expressiveness of probabilistic modal logics
I will show new proofs of expressiveness of modal logics for probabilistic bisimulation and simulation on continuous-state Labelled Markov Processes, with a new result about Polish spaces on the way. This is joint work with …
10 maja 2017 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
Characterisation of regular tree languages on the second level of Borel hierarchy
I will speak about a new result providing a relatively simple effective characterisation of regular tree languages that belong to the second level of the Borel hierarchy. The result is a next step after a …
12 kwietnia 2017 14:15
Joanna Ochremiak (Universite Paris Diderot)
Proof complexity of constraint satisfaction problems (joint work with Albert Atserias)
In this talk I will define a few "popular" proof systems and argue that constraint satisfaction problems which admit small size refutations in those proof systems are exactly the constraint satisfaction problems which can be …
5 kwietnia 2017 14:15
Vincent Penelle (Uniwersytet Warszawski)
MSO + weak U
You all have already been disappointed that MSO+U is undecidable over infinite words. Today, we will show that weakening U to a predicate U_1(X) holding if the distance between two consecutive elements of X is …
29 marca 2017 14:15
Sebastian Siebertz (Uniwersytet Warszawski)
Distributed Domination on Graph Classes of Bounded Expansion
We provide a new constant factor approximation algorithm for the (connected) distance-r dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar …
22 marca 2017 14:15
Piotr Hofman (Uniwersytet Warszawski)
State equation for Data Petri Nets (joint work with Sławomir Lasota, Jerome Leroux and Patrick Totzke)
Data nets are yet another extension of Petri Nets in which the relations between consumed and produced tokens are very restricted. Unordered/Ordered Data Petri Nets (UDPN) from the theory perspective are natural and easy to …
15 marca 2017 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Definable decompositions for graphs of bounded linear clique width (joint work with Martin Grohe, and Michał Pilipczuk)
We prove that for every positive integer k, there exists an mso1-transduction which inputs a graph of linear cliquewidth at most k and outputs, nondeterministically, some clique decomposition of the graph of width bounded by …
8 marca 2017 14:15
Thomas Zeume (Uniwersytet Warszawski)
Reachability is in DynFO
In the talk I will gently introduce the dynamic descriptive complexity framework by Patnaik and Immerman. In their formalisation, the result of a database query is updated by logical formulas after the insertion or deletion …
1 marca 2017 14:15
Paweł Parys (Uniwersytet Warszawski)
Deciding Parity Games in Quasipolynomial Time
It is a long-standing open problem whether parity games can be solved in polynomial time. I will present a recent paper by Calude, Jain, Khoussainov, Li, Stephan. They have shown an algorithm that solves a …
22 lutego 2017 14:15
Marcin Przybyłko (Uniwersytet Warszawski)
Probability of Regular Sets of Trees (joint work with Damian Niwiński and Michał Skrzypczak)
We consider the problem of computing the measure of a regular language of infinite trees with respect to so called coin-flipping measure. While the problem is unsolved in general, some progress has been made. In …