Author name cluster

Eryk Kopczyński

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

IJCAI Conference 2022 Conference Paper

Non-Euclidean Self-Organizing Maps

Dorota Celińska-Kopczyńska
Eryk Kopczyński

Self-Organizing Maps (SOMs, Kohonen networks) belong to neural network models of the unsupervised class. In this paper, we present the generalized setup for non-Euclidean SOMs. Most data analysts take it for granted to use some subregions of a flat space as their data model; however, by the assumption that the underlying geometry is non-Euclidean we obtain a new degree of freedom for the techniques that translate the similarities into spatial neighborhood relationships. We improve the traditional SOM algorithm by introducing topology-related extensions. Our proposition can be successfully applied to dimension reduction, clustering or finding similarities in big data (both hierarchical and non-hierarchical).

PDF Details DOI

IJCAI Conference 2017 Conference Paper

On the Computational Complexity of Gossip Protocols

Krzysztof R. Apt
Eryk Kopczyński
Dominik Wojtczak

Gossip protocols deal with a group of communicating agents, each holding a private information, and aim at arriving at a situation in which all the agents know each other secrets. Distributed epistemic gossip protocols are particularly simple distributed programs that use formulas from an epistemic logic. Recently, the implementability of these distributed protocols was established (which means that the evaluation of these formulas is decidable), and the problems of their partial correctness and termination were shown to be decidable, but their exact computational complexity was left open. We show that for any monotonic type of calls the implementability of a distributed epistemic gossip protocol is a P^{NP}_{||}-complete problem, while the problems of its partial correctness and termination are in coNP^{NP}.

PDF Details

Highlights Conference 2016 Conference Abstract

Programming with atoms (tool demonstration)

Eryk Kopczyński
Michał Szynwelski

A demo presentation of two simple programming languages designed to manipulate infinite, but first-order definable structures, such as the set of all intervals with rational endpoints. One of the languages is implemented as a C++ library, LOIS, by Eryk Kopczyński and Szymon Toruńczyk, while the other as a Haskell module, NLambda, by Bartek Klin and Michał Szynwelski. Internally, infinite sets are represented by logical formulas that define them, whereas an external SMT solver is invoked to check their basic properties.

Details

Highlights Conference 2015 Conference Abstract

First-order definable Constraint Satisfaction Problems

Eryk Kopczyński

First-order definable structures with atoms are infinite, but exhibit enough symmetry to be effectively manipulated. We study Constraint Satisfaction Problems (CSPs) where both the instance and the template can be definable structures with atoms. We argue that such templates and instances occur naturally in Descriptive Complexity Theory. In this talk we will concentrate on CSPs over finite templates and infinite, definable instances. In this case even decidability is not obvious, and to prove it we apply results from topological dynamics. We also prove that the complexity of solving such CSPs is one exponential level higher than the complexity of the finite CSP problem over the same template.

Details

Highlights Conference 2013 Conference Abstract

Regular graphs and the spectra of two-variable logic with counting

Eryk Kopczyński
Tony Tan

For a formula $\phi$ over a signature including predicates $P_1. .. P_k$, we define the image of $\phi$ as the set of tuples $(n_1. .. n_k)$ such that there is a model of $\phi$ where exactly $n_i$ elements satisfy $P_i$. For example, if each author has written exactly 2 papers, and each paper has exactly 3 authors, then 2*total number of authors=3*total number of authors. This can be seen as a generalization of the well known notion of a spectrum. Our main result is that, for formulae of FO2C, spectra and images are definable in Presburger arithmetic, and thus semilinear (and closed under complement).

PDF Details