Artykuły badawcze

• 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

Prace zgłoszone/przygotowywane do złożenia/w trakcie:

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

Prace dyplomowe

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

Popularyzacja matematyki:

• 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

Teksty o zadaniach z konkursów programistycznych:

• Football, Wrocławski Portal Informatyczny
• SRM 412 match summary, TopCoder
• W poszukiwaniu wyzwań. Wybór zadań z konkursów programistycznych Uniwersytetu Warszawskiego. Książka, 2012. Rozwiązania zadań "Pytania" i "Rytuał".
• W poszukiwaniu wyzwań II. Zadania z Akademickich Mistrzostw Polski w Programowaniu Zespołowym. Książka, 2015. Rozwiązania zadań "Automat", "Iloraz inteligencji" i "Kocyki".
• stworzone zadania na konkursy programistyczne: patrz tutaj

Pozostała działalność organizacyjna:

• udział w organizacji konkursów programistycznych: patrz tutaj
• 2008 - pomoc przy organizacji sympozjum projektu GAMES w Warszawie

Wygłoszone referaty:

• Principles of Programming Languages, 2017, Paryż, 19 stycznia 2017 \\ LOIS: Syntax and semantics
• Highlights of Logic, Games, and Automata, 2016, Bruksela, 8 września 2016 \\ Invisible pushdown languages
• Highlights of Logic, Games, and Automata, 2016, Bruksela, 8 września 2016 \\ Programming with atoms (tool demonstration) (invited session)
• konferencja LICS '16, Nowy Jork, 9-16 lipca 2010 \\ Invisible pushdown languages
• Forum Informatyki Teoretycznej 2016, Warszawa, 5 lutego \\ Invisible pushdown languages
• Highlights of Logic, Games, and Automata, 2015, Praga, ? września \\ First-order definable Constraint Satisfaction Problems
• DMV-PTM Joint Meeting, Poznań, 17-19 wrześniaxep 17-19, 2014 \\ Spectra of formulae with restrictions slides
• Highlights of Logic, Games, and Automata, 2014, Paris, 1-6 września \\ LOIS: a Practical C++ Library for Handling Infinite Sets slides
• Warsztaty Logiczne 2014, Białka Tatrzańska, 3-10 sierpnia \\ Hierarchia wielomianowa (i nie tylko)
• Forum Informatyki Teoretycznej 2014, Jarnołtówek, 25-27 kwietnia Apr 25-27, 2014 \\ 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, 23-29 września \\ Gry a parametry grafów
• Highlights of Logic, Games, and Automata, 2013, Paris, ? września \\ Regular graphs and the spectra of two-variable logic with counting
• Forum Informatyki Teoretycznej 2013, Toruń, 11-14 kwietnia Apr 11-14, 2013 \\ Spektra logiczne struktur o ograniczonym stopniu i planarnych
• Szkoła Zimowa Logiki i Kognitywistyki 2013, Łowicz, 3-6 stycznia \\ Aksjomat determinacji a zbiory mierzalne
• Warsztaty Logiczne 2012, Łowicz, 24-30 września \\ 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, 14-18 maja 2012 \\ Bounded degree and planar spectra (joint work with Anuj Dawar)
• International Workshop Logical Approaches to Barriers in Computing and Complexity II, Cambridge, 26-30 marca 2012 \\ Bounded degree and planar spectra (joint work with Anuj Dawar)
• konferencja CSL '11, , 12-15 września 2011 \\ Trees in trees: is the incomplete information about a tree consistent?
• University of Cambridge Computer Laboratory Wednesday Seminar, Cambridge, 11 maja 2011 \\ From deterministic finite automata to infinite games slides (PDF)
• konferencja LICS '10, Edynburg, 9-16 lipca 2010 \\ Complexity of Problems for Parikh Images of Automata (joint work with Anthony Widjaja To)
• Forum Informatyki Teoretycznej '10, Zakopane, 22-25 kwietnia 2010 \\ Złożoność problemów dla gramatyk przemiennych
• International Workshop Logical Approaches to Barriers in Computing and Complexity, Greifswald, 17-20 lutego 2010 \\ Complexity of Problems of Commutative Grammars
• Warsztaty Logiczne 2009, Poronin, 29 czerwca-5 lipca 2009 \\ PSPACE-zupełność problemu tautologicznosci w pewnych logikach
• obrona pracy doktorskiej, Warszawa, 8 kwietnia 2009 slajdy (PDF)
• Warsztaty Logiczne 2008, Wiatraki, 5-12 lipca 2008 \\ O konstrukcjach Helli
• seminarium GLoRiClass , Amsterdam, 12 czerwca 2008 \\ Half-positional Determinacy of Infinite Games slides (PDF)
• konferencja CSL+GAMES '07, Lausanne, 10-15 wrzesnia 2007 \\ Omega-Regular Half-positional winning conditions
• konferencja AutoMathA '07, Palermo, 18-22 czerwca 2007 \\ Omega-Regular Half-positional winning conditions
• Forum Informatyki Teoretycznej '07, Zakopane, 13-15 kwietnia 2007 \\ Omega-regularne półpozycyjne warunki wygrywające
• konferencja ICALP '06, Wenecja, 9-16 lipca 2006 \\ Half-positional determinacy of infinite games
• 34e École de Printemps en Informatique Théorique (EPIT 2006), Ile de Ré, 28 maja - 2 czerwca 2006 \\ Half-Positional Determinacy of Infinite Games
• Forum Informatyki Teoretycznej '06, Karpacz, 17-19 marca 2006\\ Półpozycyjne warunki wygrywające
• Dzień Doktoranta '05, Warszawa, 17 grudnia 2005 \\ Półpozycyjne warunki wygrywające
• sympozjum GAMES '05, 21-24 wrzesnia 2005 \\ Half-positionally determined winning conditions in infinite games
• kilka referatów na seminarium z teorii automatów, Warszawa
• kilka referatów na Logics and algorithms reading group, University of Cambridge, Computer Laboratory