17 Search Results for "List, Christian"

Document
DOI: 10.4230/LIPIcs.DISC.2022.26
Fast Distributed Vertex Splitting with Applications

Authors: Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part. Our techniques can be seen as the first progress towards general poly log log n-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized poly log log n-round CONGEST algorithm for (1+ε)Δ-edge coloring n-node graphs of sufficiently large constant maximum degree Δ, for any ε > 0. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.
Cite as

Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Fast Distributed Vertex Splitting with Applications. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 26:1-26:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.DISC.2022.26,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Maus, Yannic and Nolin, Alexandre},
  title =	{{Fast Distributed Vertex Splitting with Applications}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{26:1--26:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.26},
  URN =		{urn:nbn:de:0030-drops-172176},
  doi =		{10.4230/LIPIcs.DISC.2022.26},
  annote =	{Keywords: Graph problems, Edge coloring, List coloring, Lov\'{a}sz local lemma, LOCAL model, CONGEST model, Distributed computing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.45
Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP

Authors: Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We construct an oracle relative to which P = NP ∩ coNP, but there are no many-one complete sets in UP, no many-one complete disjoint NP-pairs, and no many-one complete disjoint coNP-pairs. This contributes to a research program initiated by Pudlák [P. Pudlák, 2017], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that NP ∩ coNP is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.
Cite as

Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer. Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ehrmanntraut_et_al:LIPIcs.MFCS.2022.45,
  author =	{Ehrmanntraut, Anton and Egidy, Fabian and Gla{\ss}er, Christian},
  title =	{{Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.45},
  URN =		{urn:nbn:de:0030-drops-168435},
  doi =		{10.4230/LIPIcs.MFCS.2022.45},
  annote =	{Keywords: computational complexity, promise classes, proof complexity, complete sets, oracle construction}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.10
Security Analysis of Ripple Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
The Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has one of the highest cryptocurrency market capitalizations. The Ripple consensus protocol powers this network and is generally considered to a Byzantine fault-tolerant agreement protocol, which can reach consensus in the presence of faulty or malicious nodes. In contrast to traditional Byzantine agreement protocols, there is no global knowledge of all participating nodes in Ripple consensus; instead, each node declares a list of other nodes that it trusts and from which it considers votes. Previous work has brought up concerns about the liveness and safety of the consensus protocol under the general assumptions stated initially by Ripple, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper closes this gap and makes two contributions. It first provides a detailed, abstract description of the protocol, which has been derived from the source code. Second, the paper points out that the abstract protocol may violate safety and liveness in several simple executions under relatively benign network assumptions.
Cite as

Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić. Security Analysis of Ripple Consensus. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2020.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Mi\'{c}i\'{c}, Jovana},
  title =	{{Security Analysis of Ripple Consensus}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.10},
  URN =		{urn:nbn:de:0030-drops-134956},
  doi =		{10.4230/LIPIcs.OPODIS.2020.10},
  annote =	{Keywords: Ripple, Blockchain, Quorums, Consensus}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.26
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs

Authors: Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Given an undirected graph G and integers c and k, the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most k edges in G to obtain a graph that has a proper edge coloring with at most c colors. We show that Maximum Edge-Colorable Subgraph admits, for every fixed c, a linear-size problem kernel when parameterized by the edge deletion distance of G to a graph with maximum degree c-1. This parameterization measures the distance to instances that, due to Vizing’s famous theorem, are trivial yes-instances. For c≤ 4, we also provide a linear-size kernel for the same parameterization for Multi Strong Triadic Closure, a related edge coloring problem with applications in social network analysis. We provide further results for Maximum Edge-Colorable Subgraph parameterized by the vertex deletion distance to graphs where every component has order at most c and for the list-colored versions of both problems.
Cite as

Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz. Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gruttemeier_et_al:LIPIcs.SWAT.2020.26,
  author =	{Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils},
  title =	{{Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.26},
  URN =		{urn:nbn:de:0030-drops-122731},
  doi =		{10.4230/LIPIcs.SWAT.2020.26},
  annote =	{Keywords: Graph coloring, social networks, parameterized complexity, kernelization}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.2
Latticepathology and Symmetric Functions (Extended Abstract)

Authors: Cyril Banderier, Marie-Louise Lackner, and Michael Wallner

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
In this article, we revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener - Hopf formulas, thus capturing joint distributions. We also show that each of the fundamental families of symmetric polynomials corresponds to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).
Cite as

Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and Symmetric Functions (Extended Abstract). In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2020.2,
  author =	{Banderier, Cyril and Lackner, Marie-Louise and Wallner, Michael},
  title =	{{Latticepathology and Symmetric Functions (Extended Abstract)}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.2},
  URN =		{urn:nbn:de:0030-drops-120329},
  doi =		{10.4230/LIPIcs.AofA.2020.2},
  annote =	{Keywords: Lattice path, generating function, symmetric function, algebraic function, kernel method, context-free grammar, Sparre Andersen formula, Spitzer’s identity, Wiener - Hopf factorization}
}
Document
DOI: 10.4230/DagRep.9.4.59
Ethics and Trust: Principles, Verification and Validation (Dagstuhl Seminar 19171)

Authors: Michael Fisher, Christian List, Marija Slavkovik, and Astrid Weiss

Published in: Dagstuhl Reports, Volume 9, Issue 4 (2019)

Abstract
This report documents the programme of, and outcomes from, the Dagstuhl Seminar 19171 on "Ethics and Trust: Principles, Verification and Validation". We consider the issues of ethics and trust as crucial to the future acceptance and use of autonomous systems. The development of new classes of autonomous systems, such as medical robots, "driver-less" cars, and assistive care robots has opened up questions on how we can integrate truly autonomous systems into our society. Once a system is truly autonomous, i.e. learning from interactions, moving and manipulating the world we are living in, and making decisions by itself, we must be certain that it will act in a safe and ethical way, i.e. that it will be able to distinguish 'right' from `wrong' and make the decisions we would expect of it. In order for society to accept these new machines, we must also trust them, i.e. we must believe that they are reliable and that they are trying to assist us, especially when engaged in close human-robot interaction. The seminar focused on questions of how does trust with autonomous machines evolve, how to build a `practical' ethical and trustworthy system, and what are the societal implications. Key issues included: Change of trust and trust repair, AI systems as decision makers, complex system of norms and algorithmic bias, and potential discrepancies between expectations and capabilities of autonomous machines. This workshop was a follow-up to the 2016 Dagstuhl Seminar 16222 on Engineering Moral Agents: From Human Morality to Artificial Morality. When organizing this workshop we aimed to bring together communities of researchers from moral philosophy and from artificial intelligence and extend it with researchers from (social) robotics and human-robot interaction research.
Cite as

Michael Fisher, Christian List, Marija Slavkovik, and Astrid Weiss. Ethics and Trust: Principles, Verification and Validation (Dagstuhl Seminar 19171). In Dagstuhl Reports, Volume 9, Issue 4, pp. 59-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{fisher_et_al:DagRep.9.4.59,
  author =	{Fisher, Michael and List, Christian and Slavkovik, Marija and Weiss, Astrid},
  title =	{{Ethics and Trust: Principles, Verification and Validation (Dagstuhl Seminar 19171)}},
  pages =	{59--86},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{4},
  editor =	{Fisher, Michael and List, Christian and Slavkovik, Marija and Weiss, Astrid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.4.59},
  URN =		{urn:nbn:de:0030-drops-113046},
  doi =		{10.4230/DagRep.9.4.59},
  annote =	{Keywords: Verification, Artificial Morality, Social Robotics, Machine Ethics, Autonomous Systems, Explain-able AI, Safety, Trust, Mathematical Philosophy, Robot Ethics, Human-Robot Interaction}
}
Document
DOI: 10.4230/OASIcs.LDK.2019.4
The Shortcomings of Language Tags for Linked Data When Modeling Lesser-Known Languages

Authors: Frances Gillis-Webber and Sabine Tittel

Published in: OASIcs, Volume 70, 2nd Conference on Language, Data and Knowledge (LDK 2019)

Abstract
In recent years, the modeling of data from linguistic resources with Resource Description Framework (RDF), following the Linked Data paradigm and using the OntoLex-Lemon vocabulary, has become a prevalent method to create datasets for a multilingual web of data. An important aspect of data modeling is the use of language tags to mark lexicons, lexemes, word senses, etc. of a linguistic dataset. However, attempts to model data from lesser-known languages show significant shortcomings with the authoritative list of language codes by ISO 639: for many lesser-known languages spoken by minorities and also for historical stages of languages, language codes, the basis of language tags, are simply not available. This paper discusses these shortcomings based on the examples of three such languages, i.e., two varieties of click languages of Southern Africa together with Old French, and suggests solutions for the issues identified.
Cite as

Frances Gillis-Webber and Sabine Tittel. The Shortcomings of Language Tags for Linked Data When Modeling Lesser-Known Languages. In 2nd Conference on Language, Data and Knowledge (LDK 2019). Open Access Series in Informatics (OASIcs), Volume 70, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gilliswebber_et_al:OASIcs.LDK.2019.4,
  author =	{Gillis-Webber, Frances and Tittel, Sabine},
  title =	{{The Shortcomings of Language Tags for Linked Data When Modeling Lesser-Known Languages}},
  booktitle =	{2nd Conference on Language, Data and Knowledge (LDK 2019)},
  pages =	{4:1--4:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-105-4},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{70},
  editor =	{Eskevich, Maria and de Melo, Gerard and F\"{a}th, Christian and McCrae, John P. and Buitelaar, Paul and Chiarcos, Christian and Klimek, Bettina and Dojchinovski, Milan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.LDK.2019.4},
  URN =		{urn:nbn:de:0030-drops-103682},
  doi =		{10.4230/OASIcs.LDK.2019.4},
  annote =	{Keywords: language codes, language tags, Resource Description Framework, Linked Data, Linguistic Linked Data, Khoisan languages, click languages, N|uu, ||'Au, Old French}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.33
The Online House Numbering Problem: Min-Max Online List Labeling

Authors: William E. Devanny, Jeremy T. Fineman, Michael T. Goodrich, and Tsvi Kopelowitz

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We introduce and study the online house numbering problem, where houses are added arbitrarily along a road and must be assigned labels to maintain their ordering along the road. The online house numbering problem is related to classic online list labeling problems, except that the optimization goal here is to minimize the maximum number of times that any house is relabeled. We provide several algorithms that achieve interesting tradeoffs between upper bounds on the number of maximum relabels per element and the number of bits used by labels.
Cite as

William E. Devanny, Jeremy T. Fineman, Michael T. Goodrich, and Tsvi Kopelowitz. The Online House Numbering Problem: Min-Max Online List Labeling. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{devanny_et_al:LIPIcs.ESA.2017.33,
  author =	{Devanny, William E. and Fineman, Jeremy T. and Goodrich, Michael T. and Kopelowitz, Tsvi},
  title =	{{The Online House Numbering Problem: Min-Max Online List Labeling}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.33},
  URN =		{urn:nbn:de:0030-drops-78831},
  doi =		{10.4230/LIPIcs.ESA.2017.33},
  annote =	{Keywords: house numbering, list labeling, file maintenance}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.COSIT.2017.0
Front Matter, Table of Contents, Preface, Organization, List of Authors

Authors: Eliseo Clementini, Maureen Donnelly, May Yuan, Christian Kray, Paolo Fogliaroni, and Andrea Ballatore

Published in: LIPIcs, Volume 86, 13th International Conference on Spatial Information Theory (COSIT 2017)

Abstract
Front Matter, Table of Contents, Preface, Organization, List of Authors
Cite as

13th International Conference on Spatial Information Theory (COSIT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 86, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{clementini_et_al:LIPIcs.COSIT.2017.0,
  author =	{Clementini, Eliseo and Donnelly, Maureen and Yuan, May and Kray, Christian and Fogliaroni, Paolo and Ballatore, Andrea},
  title =	{{Front Matter, Table of Contents, Preface, Organization, List of Authors}},
  booktitle =	{13th International Conference on Spatial Information Theory (COSIT 2017)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-043-9},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{86},
  editor =	{Clementini, Eliseo and Donnelly, Maureen and Yuan, May and Kray, Christian and Fogliaroni, Paolo and Ballatore, Andrea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2017.0},
  URN =		{urn:nbn:de:0030-drops-77464},
  doi =		{10.4230/LIPIcs.COSIT.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Organization, List of Authors}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.131
Testable Bounded Degree Graph Properties Are Random Order Streamable

Authors: Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in a single-pass in random order streams. Our result is obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space. We then show that our approach can also be applied to constant time approximation algorithms for bounded degree graphs in the adjacency list model: As an example, we obtain a constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error epsilon n (n is the number of nodes). Our result establishes for the first time that a large class of sublinear algorithms can be simulated in random order streams, while Omega(n) space is needed for many graph streaming problems for adversarial orders.
Cite as

Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler. Testable Bounded Degree Graph Properties Are Random Order Streamable. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 131:1-131:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{monemizadeh_et_al:LIPIcs.ICALP.2017.131,
  author =	{Monemizadeh, Morteza and Muthukrishnan, S. and Peng, Pan and Sohler, Christian},
  title =	{{Testable Bounded Degree Graph Properties Are Random Order Streamable}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{131:1--131:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.131},
  URN =		{urn:nbn:de:0030-drops-74782},
  doi =		{10.4230/LIPIcs.ICALP.2017.131},
  annote =	{Keywords: Graph streaming algorithms, graph property testing, constant-time approximation algorithms}
}
Document
DOI: 10.4230/DagRep.6.5.114
Engineering Moral Agents -- from Human Morality to Artificial Morality (Dagstuhl Seminar 16222)

Authors: Michael Fisher, Christian List, Marija Slavkovik, and Alan Winfield

Published in: Dagstuhl Reports, Volume 6, Issue 5 (2016)

Abstract
This report documents the programme of, and outcomes from, the Dagstuhl Seminar 16222 on "Engineering Moral Agents -- from Human Morality to Artificial Morality". Artificial morality is an emerging area of research within artificial intelligence (AI), concerned with the problem of designing artificial agents that behave as moral agents, i.e. adhere to moral, legal, and social norms. Context-aware, autonomous, and intelligent systems are becoming a presence in our society and are increasingly involved in making decisions that affect our lives. While humanity has developed formal legal and informal moral and social norms to govern its own social interactions, there are no similar regulatory structures that apply to non-human agents. The seminar focused on questions of how to formalise, "quantify", qualify, validate, verify, and modify the ``ethics" of moral machines. Key issues included the following: How to build regulatory structures that address (un)ethical machine behaviour? What are the wider societal, legal, and economic implications of introducing AI machines into our society? How to develop "computational" ethics and what are the difficult challenges that need to be addressed? When organising this workshop, we aimed to bring together communities of researchers from moral philosophy and from artificial intelligence most concerned with this topic. This is a long-term endeavour, but the seminar was successful in laying the foundations and connections for accomplishing it.
Cite as

Michael Fisher, Christian List, Marija Slavkovik, and Alan Winfield. Engineering Moral Agents -- from Human Morality to Artificial Morality (Dagstuhl Seminar 16222). In Dagstuhl Reports, Volume 6, Issue 5, pp. 114-137, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{fisher_et_al:DagRep.6.5.114,
  author =	{Fisher, Michael and List, Christian and Slavkovik, Marija and Winfield, Alan},
  title =	{{Engineering Moral Agents -- from Human Morality to Artificial Morality (Dagstuhl Seminar 16222)}},
  pages =	{114--137},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{5},
  editor =	{Fisher, Michael and List, Christian and Slavkovik, Marija and Winfield, Alan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.5.114},
  URN =		{urn:nbn:de:0030-drops-67236},
  doi =		{10.4230/DagRep.6.5.114},
  annote =	{Keywords: Artificial Morality, Machine Ethics, Computational Morality, Autonomous Systems, Intelligent Systems, Formal Ethics, Mathematical Philosophy, Robot Ethics}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2015.0
Front Matter, Table of Contents, Preface, Committees, List of Authors

Authors: Emmanuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Front Matter, Table of Contents, Preface, Committees, List of Authors
Cite as

19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{anceaume_et_al:LIPIcs.OPODIS.2015.0,
  author =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  title =	{{Front Matter, Table of Contents, Preface, Committees, List of Authors}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.0},
  URN =		{urn:nbn:de:0030-drops-66223},
  doi =		{10.4230/LIPIcs.OPODIS.2015.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Committees, List of Authors}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.35
Non-Blocking Doubly-Linked Lists with Good Amortized Complexity

Authors: Niloufar Shafiei

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
We present a new non-blocking doubly-linked list implementation for an asynchronous shared-memory system. It is the first such implementation for which an upper bound on amortized time complexity has been proved. In our implementation, operations access the list via cursors. Each cursor is located at an item in the list and is local to a process. In our implementation, cursors can be used to traverse and update the list, even as concurrent operations modify the list. The implementation supports two update operations, insertBefore and delete, and two move operations, moveRight and moveLeft. An insertBefore(c, x) operation inserts an item x into the list immediately before the cursor c's location. A delete(c) operation removes the item at the cursor c's location and sets the cursor to the next item in the list. The move operations move the cursor one position to the right or left. Update operations use single-word Compare&Swap instructions. Move operations only read shared memory and never change the state of the data structure. If all update operations modify different parts of the list, they run completely concurrently. A cursor is active if it is initialized, but not yet removed from the process's set of cursors. Let c.(op) be the maximum number of active cursors at any one time during the operation op. The amortized step complexity is O(c.(op)) for each update op and O(1) for each move. We provide a detailed correctness proof and amortized analysis of our implementation.
Cite as

Niloufar Shafiei. Non-Blocking Doubly-Linked Lists with Good Amortized Complexity. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{shafiei:LIPIcs.OPODIS.2015.35,
  author =	{Shafiei, Niloufar},
  title =	{{Non-Blocking Doubly-Linked Lists with Good Amortized Complexity}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.35},
  URN =		{urn:nbn:de:0030-drops-66787},
  doi =		{10.4230/LIPIcs.OPODIS.2015.35},
  annote =	{Keywords: non-blocking data structure, doubly-linked list, shared memory, amortized complexity, cursor}
}
Document
DOI: 10.4230/LIPIcs.CPM.2016.7
Graph Motif Problems Parameterized by Dual

Authors: Guillaume Fertin and Christian Komusiewicz

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Abstract
Let G=(V,E) be a vertex-colored graph, where C is the set of colors used to color V. The Graph Motif (or GM) problem takes as input G, a multiset M of colors built from C, and asks whether there is a subset S subseteq V such that (i) G[S] is connected and (ii) the multiset of colors obtained from S equals M. The Colorful Graph Motif problem (or CGM) is a constrained version of GM in which M=C, and the List-Colored Graph Motif problem (or LGM) is the extension of GM in which each vertex v of V may choose its color from a list L(v) of colors. We study the three problems GM, CGM and LGM, parameterized by l:=|V|-|M|. In particular, for general graphs, we show that, assuming the strong exponential-time hypothesis, CGM has no (2-epsilon)^l * |V|^{O(1)}-time algorithm, which implies that a previous algorithm, running in O(2^l\cdot |E|) time is optimal. We also prove that LGM is W[1]-hard even if we restrict ourselves to lists of at most two colors. If we constrain the input graph to be a tree, then we show that, in contrast to CGM, GM can be solved in O(4^l *|V|) time but admits no polynomial kernel, while CGM can be solved in O(sqrt{2}^l + |V|) time and admits a polynomial kernel.
Cite as

Guillaume Fertin and Christian Komusiewicz. Graph Motif Problems Parameterized by Dual. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fertin_et_al:LIPIcs.CPM.2016.7,
  author =	{Fertin, Guillaume and Komusiewicz, Christian},
  title =	{{Graph Motif Problems Parameterized by Dual}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{7:1--7:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.7},
  URN =		{urn:nbn:de:0030-drops-60837},
  doi =		{10.4230/LIPIcs.CPM.2016.7},
  annote =	{Keywords: NP-hard problem, subgraph problem, fixed-parameter algorithm, lowerbounds, kernelization}
}
Document
DOI: 10.4230/DagSemProc.10381.1
10381 Summary and Abstracts Collection – Robust Query Processing

Authors: Götz Graefe, Arnd Christian König, Harumi Anne Kuno, Volker Markl, and Kai-Uwe Sattler

Published in: Dagstuhl Seminar Proceedings, Volume 10381, Robust Query Processing (2011)

Abstract
Dagstuhl seminar 10381 on robust query processing (held 19.09.10 - 24.09.10) brought together a diverse set of researchers and practitioners with a broad range of expertise for the purpose of fostering discussion and collaboration regarding causes, opportunities, and solutions for achieving robust query processing. The seminar strove to build a unified view across the loosely-coupled system components responsible for the various stages of database query processing. Participants were chosen for their experience with database query processing and, where possible, their prior work in academic research or in product development towards robustness in database query processing. In order to pave the way to motivate, measure, and protect future advances in robust query processing, seminar 10381 focused on developing tests for measuring the robustness of query processing. In these proceedings, we first review the seminar topics, goals, and results, then present abstracts or notes of some of the seminar break-out sessions. We also include, as an appendix, the robust query processing reading list that was collected and distributed to participants before the seminar began, as well as summaries of a few of those papers that were contributed by some participants.
Cite as

Götz Graefe, Arnd Christian König, Harumi Anne Kuno, Volker Markl, and Kai-Uwe Sattler. 10381 Summary and Abstracts Collection – Robust Query Processing. In Robust Query Processing. Dagstuhl Seminar Proceedings, Volume 10381, pp. 1-64, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{graefe_et_al:DagSemProc.10381.1,
  author =	{Graefe, G\"{o}tz and K\"{o}nig, Arnd Christian and Kuno, Harumi Anne and Markl, Volker and Sattler, Kai-Uwe},
  title =	{{10381 Summary and Abstracts Collection – Robust Query Processing}},
  booktitle =	{Robust Query Processing},
  pages =	{1--64},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10381},
  editor =	{Goetz Graefe and Arnd Christian K\"{o}nig and Harumi Anne Kuno and Volker Markl and Kai-Uwe Sattler},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10381.1},
  URN =		{urn:nbn:de:0030-drops-29846},
  doi =		{10.4230/DagSemProc.10381.1},
  annote =	{Keywords: Robust query processing, adaptive query optimization, query execution, indexing, workload management, reliability, application availability}
}
  • Refine by Author
  • 2 Cachin, Christian
  • 2 Fisher, Michael
  • 2 Komusiewicz, Christian
  • 2 List, Christian
  • 2 Slavkovik, Marija
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Artificial intelligence
  • 1 Computing methodologies → Information extraction
  • 1 Computing methodologies → Language resources
  • 1 Information systems → Dictionaries
  • 1 Information systems → Graph-based database models
  • Show More...

  • Refine by Keyword
  • 2 Artificial Morality
  • 2 Autonomous Systems
  • 2 Front Matter
  • 2 List of Authors
  • 2 Machine Ethics
  • Show More...

  • Refine by Type
  • 17 document

  • Refine by Publication Year
  • 4 2016
  • 3 2017
  • 2 2019
  • 2 2020
  • 2 2022
  • Show More...

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