Weekly research seminar
Organizers
 prof. dr hab. Mikołaj Bojańczyk
 prof. dr hab. Damian Niwiński
Information
Wednesdays, 2:15 p.m. , room: 5050Research fields
List of talks

Jan. 9, 2008, 2:15 p.m.
Leszek Kolodziejczyk (Uniwersytet Warszawski)
The polynomial and linear time hierachies in a weak theory of arithmetic
I will show that a very weak theory of arithmetic associated with the complexity class AC^0 does not prove that the polynomial time hierarchy is equal to the linear time hierarchy. The proof uses Ajtai's …



Nov. 14, 2007, 2:15 p.m.
Andrzej Nagorko (Uniwersytet Warszawski)
Automatic groups
I'll talk about automatic groups, which incorporate finite state automata into geometric group theory in a prolific way. The class of automatic groups was introduced by Cannon and Thurston in the eighties.

Nov. 7, 2007, 2:15 p.m.
Mikolaj Bojanczyk (Uniwersytet Warszawski)
Automata and logics for data values
An XML document is commonly modeled as a tree, with nodes labeled by a finite alphabet. Properties of such documents can be expressed using finite tree automata, which are well understood and admit efficient algorithms. …

Oct. 24, 2007, 2:15 p.m.
Wojciech Czerwinski (Uniwersytet Warszawski)
Simulation between games
I will show some results of my investigations on bisimulation with a weakened winning condition for Spoiler. I will present a polynomial algorithm deciding this (modified) bisimulation between Buchi games. I will also talk about …

Oct. 17, 2007, 2:15 p.m.
Balder ten Cate (joint work with J. van Benthem and J. Vaananen) (Uniwersytet Warszawski)
Lindstrom theorems for fragments of firstorder logic
Lindstrom theorems characterize logics in terms of modeltheoretic conditions such as Compactness and the LoewenheimSkolem property. Most existing Lindstrom theorems concern extensions of firstorder logic. On the other hand, many logics relevant to computer science …

Oct. 10, 2007, 2:15 p.m.
Hugo Gimbert (joint work with F. Horn) (Uniwersytet Warszawski)
Algorithms for Solving Simple Stochastic Games
A Simple Stochastic Game is played by two players called Min and Max, moving turn by turn a pebble along edges of a graph. Player Max wants the pebble to reach a special vertexc called …

May 30, 2007, 2:15 p.m.
Paweł Parys (joint work with Krzysztof Onak) (Uniwersystet Warszawski)
Generalization of Binary Search: Searching in Trees and ForestLike Partial Orders
We extend the binary search technique to searching in trees. We consider two models of queries: questions about vertices and questions about edges. We present a general approach to this sort of problem, and apply …

May 23, 2007, 2:15 p.m.
Anna Niewiarowska (Uniwersytet Warszawski)
Probalistically Checkable Proofs and approximation hardness (continued)

May 16, 2007, 2:15 p.m.
Artur Jeż (Uniwersytet Warszawski)
Conjunctive grammars
I discuss the notion of conjunctive grammars, introduced by A. Okhotin in 2001. In short they can be described as extension of contextfree grammars with additional operation of intersection within the body of any production. …

May 9, 2007, 2:15 p.m.
Anna Niewiarowska
Probalistically Checkable Proofs and approximation hardness
The PCP theorem states that for each NP language there is a verifier that checks membership proofs probabilistically, using only logaritmic number of random bits and reading constant number of proof bits. I will show …

April 25, 2007, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Forest expressions
I will talk about a type of regular expression for unranked trees. The main focus is on connections with logic: the expressions correspond to chain logic, the starfree expressions correspond to firstorder logic, and finally, …

April 18, 2007, 2:15 p.m.
Konrad Zdanowski (Uniwersytet Warszawski)
Undecidability methods for the word problem in finite semigroups

April 3, 2007, 2:15 p.m.
Damian Niwiński (Uniwersytet Warszawski)
Two remarks on the role of ranks in parity games
These observations are of very different nature, but they can be read as evidences for the lower bound, and the upper bound, respectively. At first we show that the number of ranks gives rise to …