Notice: Undefined index: __utma in /home/staff/iinf/erykk/public_html/counter.php on line 44 Eryk Kopczyński — Publikacje
 English version  zmień styl strony

© Eryk Kopczyński  strona domowa 

Start

Badania

Studenci

Konkursy

Galeria

Gry/projekty

Linki

Kontakt

Historia

Artykuły badawcze

  • 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

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

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

Inne kierunki badań

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:

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

Start

Research

Students

Contests

Gallery

Games & projects

Links

Contact

History