Eryk Kopczyński — Research papers and other publications

Wersja polska change page style

Start

Research

Students

Programs

Contests

Gallery

Links

Contact

Research papers:

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

2006: Half-positional determinacy of infinite games. M. Bugliesi et al. (Eds.), ICALP 2006, Part II, LNCS 4052, Springer 2006, pages 336--347. 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

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.

2009: Acute triangulations of polyhedra and Rⁿ. Joint with Igor Pak and Piotr Przytycki. Preprint. Accepted to Combinatorica. PDF animations

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

2010: Omega-Regular Winning Conditions and Memory Bounds. Submitted to a journal.

2010: Ramsey's Theorem for Colors from a Metric Space. Joint with Mikołaj Bojańczyk. A short note. Submitted to a journal.

2011: Trees in trees: is the incomplete information about a tree consistent? Accepted to CSL. PDF

In progress: Bounded degree and planar spectra. Joint work with Anuj Dawar.
Abstract: Given a formula phi in some logic, the spectrum of phi, denoted spec(phi), is the set of non-negative integers n such that phi has a model of cardinality n. An interesting problem here is to characterize the set of integers which appear as a spectrum of some sentence. This problem was solved by Fagin in 1974, who has shown that S is a spectrum if and only if the set of unary representations of elements of S is in NP (equivalently, the set of binary representations of elements of S is in NE). This was one of seminal results which gave rise to the field of descriptive complexity.

What happens if we restrict our models to only bounded degree graphs, or only planar graphs?

We provide complexity theoretic characterizations of sets which are bounded degree and planar spectra of formulae. In case of bounded degree, there is a very small (polylogarythmic) gap between our lower and upper bound. In case of planar spectra (where the formula is not required to check planarity) the gap is polynomial. We also provide a weaker complexity theoretic characterization of spectra of formulae which force planarity.

In progress: 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.

In progress: Definability of linear equation systems over groups and rings. Joint work with Anuj Dawar, Erich Graedel, Bjarki Holm, and Wied Pakusa.
Abstract: Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability. All problems that we consider are solvable in polynomial time, but not expressible in fixed-point logic with counting. They also provide natural candidates for a separation of polynomial time from rank logics, which extend fixed-point logics by operators for determining the rank of definable matrices and which are sufficient for solvability problems over fields.
Based on the structure theory of finite rings, we establish logical reductions among various solvability problems. Our results indicate that {all} known solvability problems that separate FPC from PTIME can be reduced to solvability over commutative rings. Further, we prove closure properties for classes of queries that reduce to solvability over rings. As an application, these closure properties provide normal forms for logics extended with solvability operators.
In progress: FPT characterizations of the Graph Isomorphism problem. Joint work with Adam Bouland and Anuj Dawar.