Notice: Undefined index: __utma in /home/staff/iinf/erykk/public_html/counter.php on line 44 Eryk Kopczyński — Research papers and other publications
 Wersja polska  change page style

© Eryk Kopczyński  homepage 

Start

Research

Students

Contests

Gallery

Games & projects

Links

Contact

History

Research papers

  • 2017: Programming Languages in GitHub: a Visualization in Hyperbolic Plane. Joint work with Dorota Celińska. Accepted to ICWSM-17. 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 Rn. 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: On the Computational Complexity of Gossip Protocols. Joint work with Dominik Wojtczak and Krzysztof Apt. Submitted to a conference.
  • 2017: Playing with hyperbolic geometry. Joint work with Dorota Celińska and Marek Čtrnáct. Submitted to a conference.
  • 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.

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

  • 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 and Tomasz Kopczewski.

Other research topics and papers

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:

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

Start

Badania

Studenci

Konkursy

Galeria

Gry/projekty

Linki

Kontakt

Historia