Search Results

Documents authored by Kopczyński, Eryk

Found 2 Possible Name Variants:

Kopczynski, Eryk

Document
DOI: 10.4230/LIPIcs.SEA.2022.1
Discrete Hyperbolic Random Graph Model

Authors: Dorota Celińska-Kopczyńska and Eryk Kopczyński

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
The hyperbolic random graph model (HRG) has proven useful in the analysis of scale-free networks, which are ubiquitous in many fields, from social network analysis to biology. However, working with this model is algorithmically and conceptually challenging because of the nature of the distances in the hyperbolic plane. In this paper, we propose a discrete variant of the HRG model (DHRG) where nodes are mapped to the vertices of a triangulation; our algorithms allow us to work with this model in a simple yet efficient way. We present experimental results conducted on networks, both real-world and simulated, to evaluate the practical benefits of DHRG in comparison to the HRG model.
Cite as

Dorota Celińska-Kopczyńska and Eryk Kopczyński. Discrete Hyperbolic Random Graph Model. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{celinskakopczynska_et_al:LIPIcs.SEA.2022.1,
  author =	{Celi\'{n}ska-Kopczy\'{n}ska, Dorota and Kopczy\'{n}ski, Eryk},
  title =	{{Discrete Hyperbolic Random Graph Model}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.1},
  URN =		{urn:nbn:de:0030-drops-165356},
  doi =		{10.4230/LIPIcs.SEA.2022.1},
  annote =	{Keywords: hyperbolic geometry, scale-free networks, routing, tessellation}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.18
Hyperbolic Minesweeper Is in P

Authors: Eryk Kopczyński

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We show that, while Minesweeper is NP-complete, its hyperbolic variant is in P. Our proof does not rely on the rules of Minesweeper, but is valid for any puzzle based on satisfying local constraints on a graph embedded in the hyperbolic plane.
Cite as

Eryk Kopczyński. Hyperbolic Minesweeper Is in P. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 18:1-18:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kopczynski:LIPIcs.FUN.2021.18,
  author =	{Kopczy\'{n}ski, Eryk},
  title =	{{Hyperbolic Minesweeper Is in P}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{18:1--18:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.18},
  URN =		{urn:nbn:de:0030-drops-127797},
  doi =		{10.4230/LIPIcs.FUN.2021.18},
  annote =	{Keywords: Minesweeper}
}
Document
DOI: 10.4230/LIPIcs.CSL.2012.213
Definability of linear equation systems over groups and rings

Authors: Anuj Dawar, Erich Grädel, Bjarki Holm, Eryk Kopczynski, and Wied Pakusa

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

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 decidable 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 solvability problems for linear equation systems that separate fixed-point logic with counting 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.
Cite as

Anuj Dawar, Erich Grädel, Bjarki Holm, Eryk Kopczynski, and Wied Pakusa. Definability of linear equation systems over groups and rings. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 213-227, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2012.213,
  author =	{Dawar, Anuj and Gr\"{a}del, Erich and Holm, Bjarki and Kopczynski, Eryk and Pakusa, Wied},
  title =	{{Definability of linear equation systems over groups and rings}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{213--227},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.213},
  URN =		{urn:nbn:de:0030-drops-36749},
  doi =		{10.4230/LIPIcs.CSL.2012.213},
  annote =	{Keywords: inite model theory, logics with algebraic operators}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.367
Trees in Trees: Is the Incomplete Information about a Tree Consistent?

Authors: Eryk Kopczynski

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
We are interested in the following problem: given a tree automaton Aut and an incomplete tree description P, does a tree T exist such that T is accepted by Aut and consistent with P? A tree description is a tree-like structure which provides incomplete information about the shape of T. We show that this problem can be solved in polynomial time as long as Aut and the set of possible arrangements that can be forced by P are fixed. We show how our result is related to an open problem in the theory of incomplete XML information.
Cite as

Eryk Kopczynski. Trees in Trees: Is the Incomplete Information about a Tree Consistent?. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 367-380, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kopczynski:LIPIcs.CSL.2011.367,
  author =	{Kopczynski, Eryk},
  title =	{{Trees in Trees: Is the Incomplete Information about a Tree Consistent?}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{367--380},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.367},
  URN =		{urn:nbn:de:0030-drops-32434},
  doi =		{10.4230/LIPIcs.CSL.2011.367},
  annote =	{Keywords: XML, tree automata, incomplete tree descriptions, Euler cycle}
}

Kopczyński, Eryk

Document
DOI: 10.4230/LIPIcs.SEA.2022.1
Discrete Hyperbolic Random Graph Model

Authors: Dorota Celińska-Kopczyńska and Eryk Kopczyński

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
The hyperbolic random graph model (HRG) has proven useful in the analysis of scale-free networks, which are ubiquitous in many fields, from social network analysis to biology. However, working with this model is algorithmically and conceptually challenging because of the nature of the distances in the hyperbolic plane. In this paper, we propose a discrete variant of the HRG model (DHRG) where nodes are mapped to the vertices of a triangulation; our algorithms allow us to work with this model in a simple yet efficient way. We present experimental results conducted on networks, both real-world and simulated, to evaluate the practical benefits of DHRG in comparison to the HRG model.
Cite as

Dorota Celińska-Kopczyńska and Eryk Kopczyński. Discrete Hyperbolic Random Graph Model. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{celinskakopczynska_et_al:LIPIcs.SEA.2022.1,
  author =	{Celi\'{n}ska-Kopczy\'{n}ska, Dorota and Kopczy\'{n}ski, Eryk},
  title =	{{Discrete Hyperbolic Random Graph Model}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.1},
  URN =		{urn:nbn:de:0030-drops-165356},
  doi =		{10.4230/LIPIcs.SEA.2022.1},
  annote =	{Keywords: hyperbolic geometry, scale-free networks, routing, tessellation}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.18
Hyperbolic Minesweeper Is in P

Authors: Eryk Kopczyński

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We show that, while Minesweeper is NP-complete, its hyperbolic variant is in P. Our proof does not rely on the rules of Minesweeper, but is valid for any puzzle based on satisfying local constraints on a graph embedded in the hyperbolic plane.
Cite as

Eryk Kopczyński. Hyperbolic Minesweeper Is in P. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 18:1-18:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kopczynski:LIPIcs.FUN.2021.18,
  author =	{Kopczy\'{n}ski, Eryk},
  title =	{{Hyperbolic Minesweeper Is in P}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{18:1--18:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.18},
  URN =		{urn:nbn:de:0030-drops-127797},
  doi =		{10.4230/LIPIcs.FUN.2021.18},
  annote =	{Keywords: Minesweeper}
}
Document
DOI: 10.4230/LIPIcs.CSL.2012.213
Definability of linear equation systems over groups and rings

Authors: Anuj Dawar, Erich Grädel, Bjarki Holm, Eryk Kopczynski, and Wied Pakusa

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

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 decidable 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 solvability problems for linear equation systems that separate fixed-point logic with counting 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.
Cite as

Anuj Dawar, Erich Grädel, Bjarki Holm, Eryk Kopczynski, and Wied Pakusa. Definability of linear equation systems over groups and rings. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 213-227, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2012.213,
  author =	{Dawar, Anuj and Gr\"{a}del, Erich and Holm, Bjarki and Kopczynski, Eryk and Pakusa, Wied},
  title =	{{Definability of linear equation systems over groups and rings}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{213--227},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.213},
  URN =		{urn:nbn:de:0030-drops-36749},
  doi =		{10.4230/LIPIcs.CSL.2012.213},
  annote =	{Keywords: inite model theory, logics with algebraic operators}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.367
Trees in Trees: Is the Incomplete Information about a Tree Consistent?

Authors: Eryk Kopczynski

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
We are interested in the following problem: given a tree automaton Aut and an incomplete tree description P, does a tree T exist such that T is accepted by Aut and consistent with P? A tree description is a tree-like structure which provides incomplete information about the shape of T. We show that this problem can be solved in polynomial time as long as Aut and the set of possible arrangements that can be forced by P are fixed. We show how our result is related to an open problem in the theory of incomplete XML information.
Cite as

Eryk Kopczynski. Trees in Trees: Is the Incomplete Information about a Tree Consistent?. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 367-380, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kopczynski:LIPIcs.CSL.2011.367,
  author =	{Kopczynski, Eryk},
  title =	{{Trees in Trees: Is the Incomplete Information about a Tree Consistent?}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{367--380},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.367},
  URN =		{urn:nbn:de:0030-drops-32434},
  doi =		{10.4230/LIPIcs.CSL.2011.367},
  annote =	{Keywords: XML, tree automata, incomplete tree descriptions, Euler cycle}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact