Research papers

• 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. link details


• 2017: Programming Languages in GitHub: a Visualization in Hyperbolic Plane. Joint work with Dorota Celińska-Kopczyńska. Demo presentation on ICWSM-17. PDF, details.


• 2017: LOIS: syntax and semantics. Joint work with Szymon Toruńczyk. POPL 2017. See LOIS.


• 2016: LOIS: an application of SMT solvers. Joint work with Szymon Toruńczyk. SMT workshop 2016. See LOIS.


• 2016: Invisible pushdown languages. LICS 2016: 867-872. PDF


• 2015: Locally Finite Constraint Satisfaction Problems. Joint work with Bartek Klin, Joanna Ochremiak, Szymon Toruńczyk. LICS 2015: 475-486. PDF


• 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: Acute triangulations of polyhedra and Rⁿ. Joint with Igor Pak and Piotr Przytycki. Combinatorica 32 (1): 85-110. PDF animations


• 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: 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


• 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

Submitted / in preparation / work in progress:

• 2017: Hyperbolic grids and discrete random graphs. Joint work with Dorota Celińska-Kopczyńska. Work in progress. arXiv
• 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). DVI PDF
  
• 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. PS PDF
  includes results from ICALP '06 and CSL '07, and some yet unpublished results.

Popularization of mathematics:

• Hyperbolic geometry in HyperRogue. Blog.
• Szczęście w zbiorach mierzalnych, Delta nr 5/14
• Miara informacji, Delta nr 8/08
• Policz i Oblicz, Delta nr 9/06
• Rzuć monetą!, Delta nr 11/00

Texts about solutions of programming contest problems:

• Football, Wrocławski Portal Informatyczny
• SRM 412 match summary, TopCoder
• 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

Other organization:

• organizing programming competitions: see here
• 2008 - help with organizing the GAMES meeting in Warsaw

Talks:

• Principles of Programming Languages, 2017, Paris, Jan 19, 2017 \\ LOIS: Syntax and semantics
• Highlights of Logic, Games, and Automata, 2016, Brussels, Sep 9, 2016 \\ Invisible pushdown languages
• Highlights of Logic, Games, and Automata, 2016, Brussels, Sep 8, 2016 \\ Programming with atoms (tool demonstration) (invited session)
• conference LICS '16, New York City, Jul 9-16, 2010 \\ Invisible pushdown languages
• Forum Informatyki Teoretycznej 2016, Warszawa, Feb 5, 2016 \\ Invisible pushdown languages
• Highlights of Logic, Games, and Automata, 2015, Prague, Sep 18, 2015 \\ First-order definable Constraint Satisfaction Problems
• DMV-PTM Joint Meeting, Poznań, \\ Spectra of formulae with restrictions slides
• Highlights of Logic, Games, and Automata, 2014, Paris, Sep 1-6, 2014 \\ LOIS: a Practical C++ Library for Handling Infinite Sets slides
• 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?
• University of Cambridge Computer Laboratory Wednesday Seminar, Cambridge, May 11, 2011 \\ From deterministic finite automata to infinite games slides (PDF)
• 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
• PhD defense, Warsaw, Apr 8, 2009 slides in Polish (PDF)
• Warsztaty Logiczne 2008, Wiatraki, Jul 5-12, 2008 \\ O konstrukcjach Helli
• GLoRiClass seminar , Amsterdam, 12 czerwca 2008 \\ Half-positional Determinacy of Infinite Games slides (PDF)
• conference CSL+GAMES '07, Lausanne, Sep 10-15, 2007 \\ Omega-Regular Half-positional winning conditions
• conference AutoMathA '07, Palermo, Jun 18-22, 2007 \\ Omega-Regular Half-positional winning conditions
• Forum Informatyki Teoretycznej '07, Zakopane, Apr 13-15, 2007 \\ Omega-regularne półpozycyjne warunki wygrywające
• conference ICALP '06, Venice, Jul 9-16, 2006 \\ Half-positional determinacy of infinite games
• 34e École de Printemps en Informatique Théorique (EPIT 2006), Ile de Ré, May 28-Jun 2, 2006 \\ Half-Positional Determinacy of Infinite Games
• Forum Informatyki Teoretycznej '06, Karpacz, Mar 17-19, 2006\\ Półpozycyjne warunki wygrywające
• Dzień Doktoranta '05, Warszawa, Dec 17, 2005 \\ Półpozycyjne warunki wygrywające
• GAMES meeting '05, Sep 21-24, 2005 \\ Half-positionally determined winning conditions in infinite games
• some talks on automata seminar, Warsaw
• some talks on Logics and algorithms reading group, University of Cambridge, Computer Laboratory