2017: On the Computational Complexity of Gossip Protocols.
Joint work with Dominik Wojtczak
and Krzysztof Apt. IJCAI 2017.
2017: HyperRogue: Playing with Hyperbolic Geometry.
Joint work with Dorota Celińska-Kopczyńska and
Marek Čtrnáct.
Proceedings of Bridges 2017: Mathematics, Art, Music, Architecture, Education, Culture.
linkdetails
2015: Complexity of Problems of Commutative Grammars.
Logical Methods in Computer Science, Volume 11, Issue 1. A full version of the LICS paper.
(CoRR abs/1501.04245)
2015: Regular graphs and the spectra of two-variable logic with counting.
Joint work with Tony Tan. SIAM Journal on Computing (SICOMP),
44(3):786-818, 2015.
(CoRR abs/1304.0829)
2015: On the variable hierarchy of first-order spectra.
Joint work with Tony Tan. ACM Transactions on Computational Logic (ACM TOCL).
16(2):17, 2015.
(CoRR abs/1403.2225)
2015: Lower bound for Dickson's Lemma in a special case. Joint work with Wojciech Czerwiński and Tomasz Gogacz. Fundamenta Informaticae 140(2), 123-127.
2014: A simple indeterminate infinite game.
Joint work with Damian Niwiński.
Logic, Computation, Hierarchies 4, 205.
(Just what the title says.)
2013: Definability of linear equation systems over groups and rings.
Joint work with Anuj Dawar, Erich Graedel, Bjarki Holm, and Wied Pakusa.
A full version of the CSL paper.
Logical Methods in Computer Science 9 (4:12), 2013.
On Tractable Parameterizations of Graph Isomorphism.
Joint work with Adam Bouland and Anuj Dawar.
IPEC 2012, pp 218-230.PDF
2012: Definability of linear equation systems over groups and rings.
Joint work with Anuj Dawar, Erich Graedel, Bjarki Holm, and Wied Pakusa.
CSL 2012, pp 213-227.PDF
2012: Ramsey's Theorem for Colors from a Metric Space. Joint with Mikołaj Bojańczyk and Szymon Toruńczyk.
A short note. Semigroup Forum. August 2012, Volume 85, Issue 1, pp 182-184.
PDF
2011: Trees in trees: is the incomplete information about a tree consistent?
M. Bezem (Ed.), CSL 2011, LIPIcs vol. 12, pages 367--380.
CSL'2011. PDF
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
2007: Omega-Regular Half-positional winning conditions. J. Duparc and T.A. Henzinger (Eds.), CSL 2007, LNCS 4646, Springer 2007, pages 41--53.
PDF
2006: Half-positional determinacy of infinite games. M. Bugliesi et al. (Eds.), ICALP 2006, Part II, LNCS 4052, Springer 2006,
pages 336--347. PDF
2016: Bounded degree and planar spectra.
Joint work with Anuj Dawar.
Submitted to a journal. slides, arXiv
2010: Omega-Regular Winning Conditions and Memory Bounds. Submitted to a journal.
Logical properties of random graphs from small addable classes.
Joint work with Anuj Dawar.
arXiv
CFI construction for tournaments.
Joint work with Anuj Dawar.
Abstract:
The CFI construction constructs a family of graphs which are not distinguished
by a formula of C^k logic. In this paper we present how this construction
can be used on tournaments.
Work in progress: Individual vs. collective thought - the "islands" experiment.
Joint work with Dorota Celińska-Kopczyńska
and Tomasz Kopczewski.
Theses
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).
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.
The ultimate problem set from the University of Warsaw Programming Competitions. Book, 2012. Solutions of "Questions" and "Ritual".
W poszukiwaniu wyzwań II. Zadania z Akademickich Mistrzostw Polski w Programowaniu Zespołowym. Book, 2015. Solutions of "Automat", "Intelligence Quotient" and "Blankets".
created problems for programming competitions: see here
Highlights of Logic, Games, and Automata, 2014, Paris, Sep 1-6, 2014 \\ LOIS: a Practical C++ Library for Handling Infinite Setsslides
Warsztaty Logiczne 2014, Białka Tatrzańska, Aug 3-10, 2014 \\ Hierarchia wielomianowa (i nie tylko)
Forum Informatyki Teoretycznej 2014, Jarnołtówek, \\ LOIS: zbiory nieskończone w praktyce
Feb 11, 2014, Aachen, Germany (during a research visit) \\ Zero-one laws and random planar graphs
Warsztaty Logiczne 2013, Łowicz, Sep 23-29, 2013 \\ Gry a parametry grafów
Highlights of Logic, Games, and Automata, 2013, Paris, Sep ?, 2013 \\ Regular graphs and the spectra of two-variable logic with counting
Forum Informatyki Teoretycznej 2013, Toruń, \\ Spektra logiczne struktur o ograniczonym stopniu i planarnych
Szkoła Zimowa Logiki i Kognitywistyki 2013, Łowicz, Jan 3-6, 2013 \\ Aksjomat determinacji a zbiory mierzalne
Warsztaty Logiczne 2012, Łowicz, Sep 24-30, 2012 \\ Spektra dla grafów planarnych i o ograniczonym stopniu oraz Definiowalność układów równań liniowych nad grupami i pierścieniami
Workshop Finite Model Theory 2012, Les Houches, May 14-18, 2012 \\ Bounded degree and planar spectra (joint work with Anuj Dawar)
International Workshop Logical Approaches to Barriers in Computing and Complexity II, Cambridge, Mar 26-30, 2012 \\ Bounded degree and planar spectra (joint work with Anuj Dawar)
conference CSL '11, Bergen, Sep 12-15, 2011 \\ Trees in trees: is the incomplete information about a tree consistent?
conference LICS '10, Edinburgh, Jul 9-16, 2010 \\ Complexity of Problems for Parikh Images of Automata (joint work with Anthony Widjaja To)
Forum Informatyki Teoretycznej '10, Zakopane, Apr 22-25, 2010 \\ Złożoność problemów dla gramatyk przemiennych
International Workshop Logical Approaches to Barriers in Computing and Complexity, Greifswald, Feb 17-20, 2010 \\ Complexity of Problems of Commutative Grammars
Warsztaty Logiczne 2009, Poronin, Jun 29-Jul 5, 2009 \\ PSPACE-zupełność problemu tautologicznosci w pewnych logikach