152 Search Results for "Vollmer, Heribert"

Volume

LIPIcs, Volume 66

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

STACS 2017, March 8-11, 2017, Hannover, Germany

Editors: Heribert Vollmer and Brigitte Vallée

Volume

LIPIcs, Volume 47

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

STACS 2016, February 17-20, 2016, Orléans, France

Editors: Nicolas Ollinger and Heribert Vollmer

Document
DOI: 10.4230/LIPIcs.MFCS.2022.38
Enumeration Classes Defined by Circuits

Authors: Nadia Creignou, Arnaud Durand, and Heribert Vollmer

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

Abstract
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.
Cite as

Nadia Creignou, Arnaud Durand, and Heribert Vollmer. Enumeration Classes Defined by Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{creignou_et_al:LIPIcs.MFCS.2022.38,
  author =	{Creignou, Nadia and Durand, Arnaud and Vollmer, Heribert},
  title =	{{Enumeration Classes Defined by Circuits}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{38:1--38:14},
  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.38},
  URN =		{urn:nbn:de:0030-drops-168364},
  doi =		{10.4230/LIPIcs.MFCS.2022.38},
  annote =	{Keywords: Computational complexity, enumeration problem, Boolean circuit}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.19
Counting of Teams in First-Order Team Logics

Authors: Anselm Haak, Juha Kontinen, Fabian Müller, Heribert Vollmer, and Fan Yang

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study descriptive complexity of counting complexity classes in the range from #P to #*NP. A corollary of Fagin’s characterization of NP by existential second-order logic is that #P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. In this paper we extend this study to classes beyond #P and extensions of first-order logic with team semantics. These team-based logics are closely related to existential second-order logic and its fragments, hence our results also shed light on the complexity of counting for extensions of first-order logic in Tarski’s semantics. Our results show that the class #*NP can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of #*NP and #P, respectively. We also study the function class generated by inclusion logic and relate it to the complexity class TotP, which is a subclass of #P. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean Sigma_1-formulae is #*NP-complete with respect to Turing reductions as well as complete for the function class generated by dependence logic with respect to first-order reductions.
Cite as

Anselm Haak, Juha Kontinen, Fabian Müller, Heribert Vollmer, and Fan Yang. Counting of Teams in First-Order Team Logics. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haak_et_al:LIPIcs.MFCS.2019.19,
  author =	{Haak, Anselm and Kontinen, Juha and M\"{u}ller, Fabian and Vollmer, Heribert and Yang, Fan},
  title =	{{Counting of Teams in First-Order Team Logics}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.19},
  URN =		{urn:nbn:de:0030-drops-109634},
  doi =		{10.4230/LIPIcs.MFCS.2019.19},
  annote =	{Keywords: team-based logics, counting classes, finite model theory, descriptive complexity}
}
Document
DOI: 10.4230/DagRep.9.1.28
Logics for Dependence and Independence (Dagstuhl Seminar 19031)

Authors: Erich Grädel, Phokion G. Kolaitis, Juha Kontinen, and Heribert Vollmer

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

Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 19031 "Logics for Dependence and Independence". This seminar served as a follow-up seminar to the highly successful seminars "Dependence Logic: Theory and Applications" (13071) and "Logics for Dependence and Independence" (15261). A key objective of the seminar was to bring together researchers working in dependence logic and in the application areas so that they can communicate state-of-the-art advances and embark on a systematic interaction. The goal was especially to reach those researchers who have recently started working in this thriving area as well as researchers working on several aspects of database theory, separation logic, and logics of uncertainy.
Cite as

Erich Grädel, Phokion G. Kolaitis, Juha Kontinen, and Heribert Vollmer. Logics for Dependence and Independence (Dagstuhl Seminar 19031). In Dagstuhl Reports, Volume 9, Issue 1, pp. 28-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{gradel_et_al:DagRep.9.1.28,
  author =	{Gr\"{a}del, Erich and Kolaitis, Phokion G. and Kontinen, Juha and Vollmer, Heribert},
  title =	{{Logics for Dependence and Independence (Dagstuhl Seminar 19031)}},
  pages =	{28--46},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{1},
  editor =	{Gr\"{a}del, Erich and Kolaitis, Phokion G. and Kontinen, Juha and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.1.28},
  URN =		{urn:nbn:de:0030-drops-105682},
  doi =		{10.4230/DagRep.9.1.28},
  annote =	{Keywords: dependence logic, mathematical logic, computational complexity, finite model theory, game theory}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2017
LIPIcs, Volume 66, STACS'17, Complete Volume

Authors: Heribert Vollmer and Brigitte Vallée

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
LIPIcs, Volume 66, STACS'17, Complete Volume
Cite as

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{vollmer_et_al:LIPIcs.STACS.2017,
  title =	{{LIPIcs, Volume 66, STACS'17, Complete Volume}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017},
  URN =		{urn:nbn:de:0030-drops-70366},
  doi =		{10.4230/LIPIcs.STACS.2017},
  annote =	{Keywords: Models of Computation, Nonnumerical Algorithms and Problems, Mathematical Logic, Formal Languages, Combinatorics, Graph Theory}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2017.0
Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers

Authors: Heribert Vollmer and Brigitte Vallée

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers
Cite as

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{vollmer_et_al:LIPIcs.STACS.2017.0,
  author =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  title =	{{Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.0},
  URN =		{urn:nbn:de:0030-drops-70327},
  doi =		{10.4230/LIPIcs.STACS.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2017.1
Computational Aspects of Logics in Team Semantics (Tutorial)

Authors: Juha Kontinen

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Team Semantics is a logical framework for the study of various dependency notions that are important in many areas of science. The starting point of this research is marked by the publication of the monograph Dependence Logic (Jouko Väänänen, 2007) in which first-order dependence logic is developed and studied. Since then team semantics has evolved into a flexible framework in which numerous logics have been studied. Much of the work in team semantics has so far focused on results concerning either axiomatic characterizations or the expressive power and computational aspects of various logics. This tutorial provides an introduction to team semantics with a focus on results regarding expressivity and computational aspects of the most prominent logics of the area. In particular, we discuss dependence, independence and inclusion logics in first-order, propositional, and modal team semantics. We show that first-order dependence and independence logic are equivalent with existential second-order logic and inclusion logic with greatest fixed point logic. In the propositional and modal settings we characterize the expressive power of these logics by so-called team bisimulations and determine the complexity of their model checking and satisfiability problems.
Cite as

Juha Kontinen. Computational Aspects of Logics in Team Semantics (Tutorial). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kontinen:LIPIcs.STACS.2017.1,
  author =	{Kontinen, Juha},
  title =	{{Computational Aspects of Logics in Team Semantics}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.1},
  URN =		{urn:nbn:de:0030-drops-70333},
  doi =		{10.4230/LIPIcs.STACS.2017.1},
  annote =	{Keywords: team semantics, dependence logic, model checking, satisfiability problem, team bisimulation}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2017.2
Recompression: New Approach to Word Equations and Context Unification (Invited Talk)

Authors: Artur Jez

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Word equations is given by two strings over disjoint alphabets of letters and variables and we ask whether there is a substitution that satisfies this equation. Recently, a new PSPACE solution to this problem was proposed, it is based on compressing simple substrings of the equation and modifying the equation so that such operations are sound. The analysis focuses on the way the equation is stored and changed rather than on the combinatorics of words. This approach greatly simplified many existing proofs and algorithms. In particular, unlike the previous solutions, it generalises to equations over contexts (known for historical reasons as context unification): contexts are terms with one special symbol that represent a missing argument and they can be applied on terms, in which case their argument replaces the special constant.
Cite as

Artur Jez. Recompression: New Approach to Word Equations and Context Unification (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 2:1-2:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.STACS.2017.2,
  author =	{Jez, Artur},
  title =	{{Recompression: New Approach to Word Equations and Context Unification}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{2:1--2:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.2},
  URN =		{urn:nbn:de:0030-drops-70280},
  doi =		{10.4230/LIPIcs.STACS.2017.2},
  annote =	{Keywords: Word equations, exponent of periodicity, semantic unification, string unification, context unification, compression}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2017.3
Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk)

Authors: Antoine Joux

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
The discrete logarithm problem is one of the few hard problems on which public-key cryptography can be based. It was introduced in the field by the famous Diffie-Hellman key exchange protocol. Initially, the cryptographic use of the problem was considered in prime fields, but was readily generalized to arbitrary finite fields and, later, to elliptic or higher genus curves. In this talk, we survey the key technical ideas that can be used to compute discrete logarithms, especially in the case of small characteristic finite fields. These ideas stem from about 40 years of research on the topic. They appeared along the long road that leads from the initial belief that this problem was hard enough for cryptographic purpose to the current state of the art where it can no longer be considered for cryptographic use. Indeed, after the recent developments started in 2012, we now have some very efficient practical algorithms to solve this problem. Unfortunately, these algorithms remain heuristic and one important direction for future research is to lift the remaining heuristic assumptions.
Cite as

Antoine Joux. Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{joux:LIPIcs.STACS.2017.3,
  author =	{Joux, Antoine},
  title =	{{Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.3},
  URN =		{urn:nbn:de:0030-drops-70313},
  doi =		{10.4230/LIPIcs.STACS.2017.3},
  annote =	{Keywords: Cryptography, Discrete logarithms, Finite fields}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2017.4
Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk)

Authors: Till Tantau

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Algorithmic metatheorems state that if a problem can be described in a certain logic and the inputs are structured in a certain way, then the problem can be solved with a certain amount of resources. As an example, by Courcelle's Theorem all monadic second-order ("in a certain logic") properties of graphs of bounded tree width ("structured in a certain way") can be solved in linear time ("with a certain amount of resources"). Such theorems have become a valuable tool in algorithmics: If a problem happens to have the right structure and can be described in the right logic, they immediately yield a (typically tight) upper bound on the time complexity of the problem. Perhaps even more importantly, several complex algorithms rely on algorithmic metatheorems internally to solve subproblems, which considerably broadens the range of applications of these theorems. The talk is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space classes and parallel computation, and tries to give a flavor of the range of
Cite as

Till Tantau. Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 4:1-4:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{tantau:LIPIcs.STACS.2017.4,
  author =	{Tantau, Till},
  title =	{{Applications of Algorithmic Metatheorems to Space Complexity and Parallelism}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{4:1--4:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.4},
  URN =		{urn:nbn:de:0030-drops-70303},
  doi =		{10.4230/LIPIcs.STACS.2017.4},
  annote =	{Keywords: Algorithmic metatheorems, Courcelle’s Theorem, tree width, monadic second-order logic, logarithmic space, parallel computations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.5
Split Contraction: The Untold Story

Authors: Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
The edit operation that contracts edges, which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of Parameterized Complexity. In this paper, we examine an important family of graphs, namely the family of split graphs, which in the context of edge contractions, is proven to be significantly less obedient than one might expect. Formally, given a graph G and an integer k, the Split Contraction problem asks whether there exists a subset X of edges of G such that G/X is a split graph and X has at most k elements. Here, G/X is the graph obtained from G by contracting edges in X. It was previously claimed that the Split Contraction problem is fixed-parameter tractable. However, we show that, despite its deceptive simplicity, it is W[1]-hard. Our main result establishes the following conditional lower bound: under the Exponential Time Hypothesis, the Split Contraction problem cannot be solved in time 2^(o(l^2)) * poly(n) where l is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the first tight lower bound of the form 2^(o(l^2)) * poly(n) for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest.
Cite as

Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split Contraction: The Untold Story. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.STACS.2017.5,
  author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Split Contraction: The Untold Story}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.5},
  URN =		{urn:nbn:de:0030-drops-70297},
  doi =		{10.4230/LIPIcs.STACS.2017.5},
  annote =	{Keywords: Split Graph, Parameterized Complexity, Edge Contraction}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.6
The Operator Approach to Entropy Games

Authors: Marianne Akian, Stéphane Gaubert, Julien Grand-Clément, and Jérémie Guillaud

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Entropy games and matrix multiplication games have been recently introduced by Asarin et al. They model the situation in which one player (Despot) wishes to minimize the growth rate of a matrix product, whereas the other player (Tribune) wishes to maximize it. We develop an operator approach to entropy games. This allows us to show that entropy games can be cast as stochastic mean payoff games in which some action spaces are simplices and payments are given by a relative entropy (Kullback-Leibler divergence). In this way, we show that entropy games with a fixed number of states belonging to Despot can be solved in polynomial time. This approach also allows us to solve these games by a policy iteration algorithm, which we compare with the spectral simplex algorithm developed by Protasov.
Cite as

Marianne Akian, Stéphane Gaubert, Julien Grand-Clément, and Jérémie Guillaud. The Operator Approach to Entropy Games. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{akian_et_al:LIPIcs.STACS.2017.6,
  author =	{Akian, Marianne and Gaubert, St\'{e}phane and Grand-Cl\'{e}ment, Julien and Guillaud, J\'{e}r\'{e}mie},
  title =	{{The Operator Approach to Entropy Games}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.6},
  URN =		{urn:nbn:de:0030-drops-70260},
  doi =		{10.4230/LIPIcs.STACS.2017.6},
  annote =	{Keywords: Stochastic games, Shapley operators, policy iteration, Perron eigenvalues, Risk sensitive control}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.7
Parameterized Complexity of Small Weight Automorphisms

Authors: Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We show that checking if a given hypergraph has an automorphism that moves exactly k vertices is fixed parameter tractable, using k and additionally either the maximum hyperedge size or the maximum color class size as parameters. In particular, it suffices to use k as parameter if the hyperedge size is at most polylogarithmic in the size of the given hypergraph. As a building block for our algorithms, we generalize Schweitzer's FPT algorithm [ESA 2011] that, given two graphs on the same vertex set and a parameter k, decides whether there is an isomorphism between the two graphs that moves at most k vertices. We extend this result to hypergraphs, using the maximum hyperedge size as a second parameter. Another key component of our algorithm is an orbit-shrinking technique that preserves permutations that move few points and that may be of independent interest. Applying it to a suitable subgroup of the automorphism group allows us to switch from bounded hyperedge size to bounded color classes in the exactly-k case.
Cite as

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Parameterized Complexity of Small Weight Automorphisms. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.STACS.2017.7,
  author =	{Arvind, Vikraman and K\"{o}bler, Johannes and Kuhnert, Sebastian and Tor\'{a}n, Jacobo},
  title =	{{Parameterized Complexity of Small Weight Automorphisms}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.7},
  URN =		{urn:nbn:de:0030-drops-70278},
  doi =		{10.4230/LIPIcs.STACS.2017.7},
  annote =	{Keywords: Parameterized algorithms, hypergraph isomorphism.}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.8
What Can Be Verified Locally?

Authors: Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, and Dennis Olivetti

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We are considering distributed network computing, in which computing entities are connected by a network modeled as a connected graph. These entities are located at the nodes of the graph, and they exchange information by message-passing along its edges. In this context, we are adopting the classical framework for local distributed decision, in which nodes must collectively decide whether their network configuration satisfies some given boolean predicate, by having each node interacting with the nodes in its vicinity only. A network configuration is accepted if and only if every node individually accepts. It is folklore that not every Turing-decidable network property (e.g., whether the network is planar) can be decided locally whenever the computing entities are Turing machines (TM). On the other hand, it is known that every Turing-decidable network property can be decided locally if nodes are running non-deterministic Turing machines (NTM). However, this holds only if the nodes have the ability to guess the identities of the nodes currently in the network. That is, for different sets of identities assigned to the nodes, the correct guesses of the nodes might be different. If one asks the nodes to use the same guess in the same network configuration even with different identity assignments, i.e., to perform identity-oblivious guesses, then it is known that not every Turing-decidable network property can be decided locally. In this paper, we show that every Turing-decidable network property can be decided locally if nodes are running alternating Turing machines (ATM), and this holds even if nodes are bounded to perform identity-oblivious guesses. More specifically, we show that, for every network property, there is a local algorithm for ATMs, with at most 2 alternations, that decides that property. To this aim, we define a hierarchy of classes of decision tasks where the lowest level contains tasks solvable with TMs, the first level those solvable with NTMs, and level k contains those tasks solvable with ATMs with k alternations. We characterize the entire hierarchy, and show that it collapses in the second level. In addition, we show separation results between the classes of network properties that are locally decidable with TMs, NTMs, and ATMs. Finally, we establish the existence of completeness results for each of these classes, using novel notions of local reduction.
Cite as

Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, and Dennis Olivetti. What Can Be Verified Locally?. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.STACS.2017.8,
  author =	{Balliu, Alkida and D'Angelo, Gianlorenzo and Fraigniaud, Pierre and Olivetti, Dennis},
  title =	{{What Can Be Verified Locally?}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.8},
  URN =		{urn:nbn:de:0030-drops-70253},
  doi =		{10.4230/LIPIcs.STACS.2017.8},
  annote =	{Keywords: Distributed Network Computing, Distributed Algorithm, Distributed Decision, Locality}
}
  • Refine by Author
  • 24 Vollmer, Heribert
  • 8 Kontinen, Juha
  • 6 Creignou, Nadia
  • 5 Lokshtanov, Daniel
  • 5 Saurabh, Saket
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Complexity classes
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 10 computational complexity
  • 10 finite model theory
  • 7 lower bounds
  • 5 dependence logic
  • 5 parameterized complexity
  • Show More...

  • Refine by Type
  • 150 document
  • 2 volume

  • Refine by Publication Year
  • 64 2016
  • 62 2017
  • 7 2006
  • 6 2007
  • 6 2010
  • 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