Start
Badania
Studenci
Programy
Konkursy
Galeria
Linki
Kontakt
|
|
Artykuły naukowe:
- 1999-2004: Konstrukcja i własności ridgeletów. Praca magisterska (na matematyce).
DVI
PDF
- 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.
Praca doktorska
pod kierunkiem
Damiana Niwińskiego.
PS
PDF
zawiera wyniki z ICALP '06 i CSL '07, a także kilka innych
jeszcze nieopublikowanych wyników.
- 2009: Acute triangulations of polyhedra and Rn.
Joint with Igor Pak
and Piotr Przytycki.
Preprint. Accepted to Combinatorica. PDF
animations
- 2010: Acute triangulations of polyhedra and the Euclidean space.
Joint with Igor Pak
and Piotr Przytycki.
Procs of Annual Symposium of Computational Geometry,
pages 307--313. (Extended abstract of the previous paper.)
- 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.
Artykuły popularnonaukowe:
- Rzuć monetą!, Delta nr 11/00
- Policz i Oblicz, Delta nr 9/06
- Miara informacji, Delta nr 8/08
Artykuły w Internecie:
Wygłoszone referaty:
- sympozjum GAMES '05, 21-24 wrzesnia 2005 \\
Half-positionally determined winning conditions in infinite games
- Dzień Doktoranta '05, Warszawa, 17 grudnia 2005 \\
Półpozycyjne warunki wygrywające
- Forum Informatyki Teoretycznej '06, Karpacz, 17-19 marca 2006\\
Półpozycyjne warunki wygrywające
- 34e École de Printemps en Informatique Théorique (EPIT 2006),
Ile de Ré, 28 maja - 2 czerwca 2006 \\
Half-Positional Determinacy of Infinite Games
- konferencja ICALP '06, Wenecja, 9-16 lipca 2006 \\
Half-positional determinacy of infinite games
- Forum Informatyki Teoretycznej '07, Zakopane, 13-15 kwietnia 2007 \\
Omega-regularne półpozycyjne warunki wygrywające
- konferencja AutoMathA '07, Palermo, 18-22 czerwca 2007 \\
Omega-Regular Half-positional winning conditions
- konferencja CSL+GAMES '07, Lausanne, 10-15 wrzesnia 2007 \\
Omega-Regular Half-positional winning conditions
- seminarium GLoRiClass
, Amsterdam, 12 czerwca 2008 \\
Half-positional Determinacy of Infinite Games slides (PDF)
-
Warsztaty Logiczne 2008, Wiatraki, 5-12 lipca 2008 \\
O konstrukcjach Helli
- obrona pracy doktorskiej, Warszawa, 8 kwietnia 2009
slajdy (PDF)
- Warsztaty Logiczne 2009, Poronin, 29 czerwca-5 lipca 2009 \\
PSPACE-zupełność problemu tautologicznosci w pewnych logikach
- International Workshop
Logical Approaches to Barriers in Computing and Complexity, Greifswald, 17-20 lutego 2010 \\
Complexity of Problems of Commutative Grammars
- Forum Informatyki Teoretycznej '10, Zakopane, 22-25 kwietnia 2010 \\
Złożoność problemów dla gramatyk przemiennych
- konferencja LICS '10, Edynburg, 9-16 lipca 2010 \\
Complexity of Problems for Parikh Images of Automata (joint work with Anthony Widjaja To)
- University of Cambridge Computer Laboratory Wednesday Seminar,
Cambridge, 11 maja 2011 \\
From deterministic finite automata to infinite games slides (PDF)
- kilka referatów na
seminarium z teorii automatów, Warszawa
- kilka referatów na
Logics and algorithms reading group,
University of Cambridge, Computer Laboratory
Zadania na konkursy programistyczne:
Pozostała działalność organizacyjna:
- 2008 -
pomoc przy organizacji sympozjum projektu GAMES w Warszawie
| |
|
Start
Research
Students
Programs
Contests
Gallery
Links
Contact
|
