1999-2004: Konstrukcja i własności ridgeletów. Praca magisterska (na matematyce).
DVIPDF
1999-2005: Półpozycyjnie zdeterminowane warunki wygrywające w grach nieskończonych. Praca magisterska (na informatyce).
2006: Half-positional determinacy of infinite games. M. Bugliesi et al. (Eds.), ICALP 2006, Part II, LNCS 4052, Springer 2006,
pages 336--347. PDF
2007: Omega-Regular Half-positional winning conditions. J. Duparc and T.A. Henzinger (Eds.), CSL 2007, LNCS 4646, Springer 2007, pages 41--53.
PDF
2005-2009: Half-positional determinacy of infinite games.
PhD thesis
under supervision of
Damian Niwiński.
PSPDF
includes results from ICALP '06 and CSL '07, and some yet unpublished
results.
2010: Complexity of Problems for Commutative Grammars.
Preprint at arXiv:1003.4105v1.
Accepted for LICS'2010 after merging with Anthony Widjaja To's paper.
2010: Complexity of Problems for Parikh Images of Automata.
Joint with Anthony Widjaja To.
LICS '2010, pages 80--89,
2010 25th Annual IEEE Symposium on Logic in Computer Science. PDF
2010: Omega-Regular Winning Conditions and Memory Bounds.
Submitted to a journal.
2010: Ramsey's Theorem for Colors from a Metric Space. Joint with Mikołaj Bojańczyk.
A short note. Submitted to a journal.
2011: Trees in trees: is the incomplete information about a tree consistent?
Accepted to CSL. PDF
In progress: Bounded degree and planar spectra.
Joint work with Anuj Dawar.
Abstract:
Given a formula phi in some logic, the spectrum of phi, denoted spec(phi), is the set of non-negative integers n such that phi has a model of cardinality n. An interesting problem here is to characterize the set of integers which appear as a spectrum of some sentence. This problem was solved by Fagin in 1974, who has shown that S is a spectrum if and only if the set of unary representations of elements of S is in NP (equivalently, the set of binary representations of elements of S is in NE). This was one of seminal results which gave rise to the field of descriptive complexity.
What happens if we restrict our models to only bounded degree graphs, or only planar graphs?
We provide complexity theoretic characterizations of sets which are bounded degree and planar spectra of formulae. In case of bounded degree, there is a very small (polylogarythmic) gap between our lower and upper bound. In case of planar spectra (where the formula is not required to check planarity) the gap is polynomial. We also provide a weaker complexity theoretic characterization of spectra of formulae which force planarity.
In progress: Zero-one and limit laws for FO and MSO on random planar graphs.
Joint work with Anuj Dawar.
Abstract:
It is well known that first order logic admits a zero one law: a probability that a random structure of size n tends to a limit of either 0 or 1 as n tends to infinity. The same property holds for other logics, like the infinitary logic L_\infty.
A similar result is also known for MSO logic on random free labelled trees (McColm). On the other hand, if we consider
random rooted labelled trees, then the probability tends to a limit which need not be 0 or 1 \cite (Woods).
Similar limit laws hold for the class of d-regular graphs, or where degrees of vertices have a specific distribution
(Lynch).
What happens for random planar graphs?
Technically, all the techniques we are using come from previous papers: we are just merging the logical techniques of
McColm with the probabilistic and combinatorial results about random planar graphs of McDiarmid, Steger and Welsh.
In progress: Definability of linear equation systems over groups and rings.
Joint work with Anuj Dawar, Erich Graedel, Bjarki Holm, and Wied Pakusa.
Abstract:
Motivated by the quest for a logic for PTIME and
recent insights that the descriptive complexity of problems from
linear algebra is a crucial aspect of this problem,
we study the solvability of linear equation systems over
finite groups and rings from the viewpoint of
logical (inter-)definability. All problems that we
consider are solvable in polynomial time, but not
expressible in fixed-point logic with counting. They also
provide natural candidates for a separation of
polynomial time from rank logics, which extend
fixed-point logics by operators for determining the rank of definable
matrices and which are sufficient for solvability problems
over fields.
Based on the structure theory of finite rings, we establish logical
reductions among various solvability problems.
Our results indicate that {all} known solvability problems
that separate FPC from PTIME can be reduced to solvability over
commutative rings.
Further, we prove closure properties for classes of queries that
reduce to solvability over rings. As an application, these closure properties provide normal forms
for logics extended with solvability operators.
In progress: FPT characterizations of the Graph Isomorphism problem.
Joint work with Adam Bouland and Anuj Dawar.
Warsztaty Logiczne 2009, Poronin, Jun 29-Jul 5, 2009 \\
PSPACE-zupełność problemu tautologicznosci w pewnych logikach
International Workshop
Logical Approaches to Barriers in Computing and Complexity, Greifswald, Feb 17-20, 2010 \\
Complexity of Problems of Commutative Grammars
Forum Informatyki Teoretycznej '10, Zakopane, Apr 22-25, 2010 \\
Złożoność problemów dla gramatyk przemiennych
conference LICS '10, Edinburgh, Jul 9-16, 2010 \\
Complexity of Problems for Parikh Images of Automata (joint work with Anthony Widjaja To)