132 Search Results for "Mayr, Ernst W."

Volume

LIPIcs, Volume 30

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

STACS 2015, March 4-7, 2015, Garching, Germany

Editors: Ernst W. Mayr and Nicolas Ollinger

Volume

LIPIcs, Volume 25

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

STACS 2014, March 5-8, 2014, Lyon, France

Editors: Ernst W. Mayr and Natacha Portier

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.131
Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality

Authors: Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Węgrzycki

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, '78) and is EXPSPACE-hard already under unary encodings (Lipton, '76). More precisely, Rosier and Yen later utilise Rackoff’s bounding technique to show that if coverability holds then there is a run of length at most n^{2^𝒪(d log d)}, where d is the dimension and n is the size of the given unary VASS. Earlier, Lipton showed that there exist instances of coverability in d-dimensional unary VASS that are only witnessed by runs of length at least n^{2^Ω(d)}. Our first result closes this gap. We improve the upper bound by removing the twice-exponentiated log(d) factor, thus matching Lipton’s lower bound. This closes the corresponding gap for the exact space required to decide coverability. This also yields a deterministic n^{2^𝒪(d)}-time algorithm for coverability. Our second result is a matching lower bound, that there does not exist a deterministic n^{2^o(d)}-time algorithm, conditioned upon the Exponential Time Hypothesis. When analysing coverability, a standard proof technique is to consider VASS with bounded counters. Bounded VASS make for an interesting and popular model due to strong connections with timed automata. Withal, we study a natural setting where the counter bound is linear in the size of the VASS. Here the trivial exhaustive search algorithm runs in 𝒪(n^{d+1})-time. We give evidence to this being near-optimal. We prove that in dimension one this trivial algorithm is conditionally optimal, by showing that n^{2-o(1)}-time is required under the k-cycle hypothesis. In general fixed dimension d, we show that n^{d-2-o(1)}-time is required under the 3-uniform hyperclique hypothesis.
Cite as

Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Węgrzycki. Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 131:1-131:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kunnemann_et_al:LIPIcs.ICALP.2023.131,
  author =	{K\"{u}nnemann, Marvin and Mazowiecki, Filip and Sch\"{u}tze, Lia and Sinclair-Banks, Henry and W\k{e}grzycki, Karol},
  title =	{{Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{131:1--131:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.131},
  URN =		{urn:nbn:de:0030-drops-181834},
  doi =		{10.4230/LIPIcs.ICALP.2023.131},
  annote =	{Keywords: Vector Addition System, Coverability, Reachability, Fine-Grained Complexity, Exponential Time Hypothesis, k-Cycle Hypothesis, Hyperclique Hypothesis}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2015
LIPIcs, Volume 30, STACS'15, Complete Volume

Authors: Ernst W. Mayr and Nicolas Ollinger

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
LIPIcs, Volume 30, STACS'15, Complete Volume
Cite as

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{mayr_et_al:LIPIcs.STACS.2015,
  title =	{{LIPIcs, Volume 30, STACS'15, Complete Volume}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015},
  URN =		{urn:nbn:de:0030-drops-49630},
  doi =		{10.4230/LIPIcs.STACS.2015},
  annote =	{Keywords: Models of Computation, Nonnumerical Algorithms and Problems, Mathematical Logic, Formal Languages, Combinatorics, Graph Theory}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2015.i
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Ernst W. Mayr and Nicolas Ollinger

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. i-xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{mayr_et_al:LIPIcs.STACS.2015.i,
  author =	{Mayr, Ernst W. and Ollinger, Nicolas},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{i--xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.i},
  URN =		{urn:nbn:de:0030-drops-49615},
  doi =		{10.4230/LIPIcs.STACS.2015.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2015.1
Overcoming Intractability in Unsupervised Learning (Invited Talk)

Authors: Sanjeev Arora

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Unsupervised learning - i.e., learning with unlabeled data - is increasingly important given today's data deluge. Most natural problems in this domain - e.g. for models such as mixture models, HMMs, graphical models, topic models and sparse coding/dictionary learning, deep learning - are NP-hard. Therefore researchers in practice use either heuristics or convex relaxations with no concrete approximation bounds. Several nonconvex heuristics work well in practice, which is also a mystery. The talk will describe a sequence of recent results whereby rigorous approaches leading to polynomial running time are possible for several problems in unsupervised learning. The proof of polynomial running time usually relies upon nondegeneracy assumptions on the data and the model parameters, and often also on stochastic properties of the data (average-case analysis). We describe results for topic models, sparse coding, and deep learning. Some of these new algorithms are very efficient and practical - e.g. for topic modeling.
Cite as

Sanjeev Arora. Overcoming Intractability in Unsupervised Learning (Invited Talk). In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{arora:LIPIcs.STACS.2015.1,
  author =	{Arora, Sanjeev},
  title =	{{Overcoming Intractability in Unsupervised Learning}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{1--1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.1},
  URN =		{urn:nbn:de:0030-drops-49581},
  doi =		{10.4230/LIPIcs.STACS.2015.1},
  annote =	{Keywords: machine learning, unsupervised learning, intractability, NP-hardness}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2015.2
The Complexity of Constraint Satisfaction Problems (Invited Talk)

Authors: Manuel Bodirsky

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
The tractability conjecture for constraint satisfaction problems (CSPs) describes the constraint languages over a finite domain whose CSP can be solved in polynomial-time. The precise formulation of the conjecture uses basic notions from universal algebra. In this talk, we give a short introduction to the universal-algebraic approach to the study of the complexity of CSPs. Finally, we discuss attempts to generalise the tractability conjecture to large classes of constraint languages over infinite domains, in particular for constraint languages that arise in qualitative temporal and spatial reasoning.
Cite as

Manuel Bodirsky. The Complexity of Constraint Satisfaction Problems (Invited Talk). In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 2-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bodirsky:LIPIcs.STACS.2015.2,
  author =	{Bodirsky, Manuel},
  title =	{{The Complexity of Constraint Satisfaction Problems}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{2--9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.2},
  URN =		{urn:nbn:de:0030-drops-49567},
  doi =		{10.4230/LIPIcs.STACS.2015.2},
  annote =	{Keywords: constraint satisfaction, universal algebra, model theory, clones, temporal and spatial reasoning}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2015.10
Parallel Algorithms Reconsidered (Invited Talk)

Authors: Peter Sanders

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Parallel algorithms have been a subject of intensive algorithmic research in the 1980s. This research almost died out in the mid 1990s. In this paper we argue that it is high time to reconsider this subject since a lot of things have changed. First and foremost, parallel processing has moved from a niche application to something mandatory for any performance critical computer applications. We will also point out that even very fundamental results can still be obtained. We give examples and also formulate some open problems.
Cite as

Peter Sanders. Parallel Algorithms Reconsidered (Invited Talk). In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 10-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{sanders:LIPIcs.STACS.2015.10,
  author =	{Sanders, Peter},
  title =	{{Parallel Algorithms Reconsidered}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{10--18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.10},
  URN =		{urn:nbn:de:0030-drops-49572},
  doi =		{10.4230/LIPIcs.STACS.2015.10},
  annote =	{Keywords: parallel algorithm, algorithm engineering, communication efficient algorithm, polylogarithmic time algorithm, parallel machine model}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2015.19
Computational Social Choice (Tutorial)

Authors: Felix Brandt

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Over the past few years there has been a lively exchange of ideas between computer science, in particular theoretical computer science and artificial intelligence, on the one hand and economics, in particular game theory and social choice, on the other. This exchange goes in both directions and has produced active research areas such as algorithmic game theory and computational social choice. Social choice theory concerns the formal analysis and design of methods for aggregating possibly conflicting preferences such as in voting, assignment, or matching problems. Much of the work in classic social choice theory has focused on results concerning the formal possibility and impossibility of aggregation functions that combine desirable properties. This tutorial provided an overview of central results in social choice theory with a special focus on axiomatic characterizations as well as computational aspects. While some aggregation functions can be easily computed, others have been shown to be computationally intractable (e.g., NP-hard or #P-hard). Topics that were covered in this tutorial included (i) rational choice theory, (ii) Arrow's impossibility theorem, (iii) tournament solutions (such as the top cycle, the uncovered set, the Banks set, or the tournament equilibrium set), and (iv) randomized social choice functions. The overarching theme were escape routes from negative results such as Arrow's impossibility theorem.
Cite as

Felix Brandt. Computational Social Choice (Tutorial). In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, p. 19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{brandt:LIPIcs.STACS.2015.19,
  author =	{Brandt, Felix},
  title =	{{Computational Social Choice}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{19--19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.19},
  URN =		{urn:nbn:de:0030-drops-49593},
  doi =		{10.4230/LIPIcs.STACS.2015.19},
  annote =	{Keywords: social choice theory, economics, algorithms, theory}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.STACS.2015.20
Algorithmic Game Theory (Tutorial)

Authors: Paul W. Goldberg

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Game theory studies mathematical models of interactions amongst self-interested entities. A "solution concept" means a description of the outcome of a game, and it is important that it should be defined in such a way that a solution always exists (every game should have an outcome). Nash's famous theorem that mixed-strategy equilibria are guaranteed to exist, resulted in Nash equilibrium being the most prominent solution concept in game theory. As a result, computational challenges of the form "given a game, find a solution", have the property that we are searching for something whose existence is guaranteed (they are total search problems). Moreover, these solutions belong to the complexity class NP, since it is usually straightforward to check whether a proposed solution is correct (an incorrect one will admit a profitable deviation by one or more of the players, and this is usually easy to find). However, in versions of the problem that appear to be computationally hard, we cannot apply NP-completeness, due to a result of Megiddo saying that total search problems cannot be NP-complete unless NP is equal to co-NP. In this tutorial, which is intended for people familiar with NP-completeness, I give an overview of the alternative notions of computational hardness that apply to game-theoretic solution concepts. I discuss the complexity class PPAD (introduced by Papadimitriou) which captures the computational complexity of various classes of games that don’t seem to be solvable in polynomial time. I also mention the complexity classes PLS and FIXP, and the kinds of games that they apply to. Suppose, alternatively, that we have a polynomial-time algorithm that applies to some given class of games. A follow-up question is whether there exist algorithms that find a solution via processes that reflect decentralised selfish behaviour. This is because a solution concept arguably remains unrealistic if it can be efficiently computed, but only using a highly centralised algorithm. In the second half of the tutorial I present some results on learning dynamics for equilibrium computation, and mention recent work on communication complexity and query complexity. I discuss some research directions and open problems, such as the following. What are the prospects for proving that PPAD is as hard as NP? How about algorithms that find improved approximate Nash equilibria? 2-player games are easy to solve in practice, using the Lemke-Howson algorithm, so is there a satisfying mathematical sense in which 2-player games are easy to solve? (For example, a sense in which Lemke-Howson works "most of the time"?)
Cite as

Paul W. Goldberg. Algorithmic Game Theory (Tutorial). In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, p. 20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goldberg:LIPIcs.STACS.2015.20,
  author =	{Goldberg, Paul W.},
  title =	{{Algorithmic Game Theory}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{20--20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.20},
  URN =		{urn:nbn:de:0030-drops-49606},
  doi =		{10.4230/LIPIcs.STACS.2015.20},
  annote =	{Keywords: equilibrium, non-cooperative games, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.21
The Minimum Oracle Circuit Size Problem

Authors: Eric Allender, Dhiraj Holden, and Valentine Kabanets

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP^QBF is known to be complete for PSPACE under ZPP reductions. We show that it is not complete under logspace reductions, and indeed it is not even hard for TC under uniform AC^0 reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures.
Cite as

Eric Allender, Dhiraj Holden, and Valentine Kabanets. The Minimum Oracle Circuit Size Problem. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 21-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.STACS.2015.21,
  author =	{Allender, Eric and Holden, Dhiraj and Kabanets, Valentine},
  title =	{{The Minimum Oracle Circuit Size Problem}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{21--33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.21},
  URN =		{urn:nbn:de:0030-drops-49013},
  doi =		{10.4230/LIPIcs.STACS.2015.21},
  annote =	{Keywords: Kolmogorov complexity, minimum circuit size problem, PSPACE, NP-intermediate sets}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.34
Graph Searching Games and Width Measures for Directed Graphs

Authors: Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In cops and robber games a number of cops tries to capture a robber in a graph. A variant of these games on undirected graphs characterises tree width by the least number of cops needed to win. We consider cops and robber games on digraphs and width measures (such as DAG-width, directed tree width or D-width) corresponding to them. All of them generalise tree width and the game characterising it. For the DAG-width game we prove that the problem to decide the minimal number of cops required to capture the robber (which is the same as deciding DAG-width), is PSPACE-complete, in contrast to most other similar games. We also show that the cop-monotonicity cost for directed tree width games cannot be bounded by any function. As a consequence, D-width is not bounded in directed tree width, refuting a conjecture by Safari. A large number of directed width measures generalising tree width has been proposed in the literature. However, only very little was known about the relation between them, in particular about whether classes of digraphs of bounded width in one measure have bounded width in another. In this paper we establish an almost complete order among the most prominent width measures with respect to mutual boundedness.
Cite as

Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Graph Searching Games and Width Measures for Directed Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 34-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{akhoondianamiri_et_al:LIPIcs.STACS.2015.34,
  author =	{Akhoondian Amiri, Saeed and Kaiser, Lukasz and Kreutzer, Stephan and Rabinovich, Roman and Siebertz, Sebastian},
  title =	{{Graph Searching Games and Width Measures for Directed Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{34--47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.34},
  URN =		{urn:nbn:de:0030-drops-49020},
  doi =		{10.4230/LIPIcs.STACS.2015.34},
  annote =	{Keywords: cops and robber games, directed graphs, DAG-width}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.48
Subset Sum in the Absence of Concentration

Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers.
Cite as

Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Subset Sum in the Absence of Concentration. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 48-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.STACS.2015.48,
  author =	{Austrin, Per and Kaski, Petteri and Koivisto, Mikko and Nederlof, Jesper},
  title =	{{Subset Sum in the Absence of Concentration}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{48--61},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.48},
  URN =		{urn:nbn:de:0030-drops-49034},
  doi =		{10.4230/LIPIcs.STACS.2015.48},
  annote =	{Keywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.62
On Sharing, Memoization, and Polynomial Time

Authors: Martin Avanzini and Ugo Dal Lago

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We study how the adoption of an evaluation mechanism with sharing and memoization impacts the class of functions which can be computed in polynomial time. We first show how a natural cost model in which lookup for an already computed result has no cost is indeed invariant. As a corollary, we then prove that the most general notion of ramified recurrence is sound for polynomial time, this way settling an open problem in implicit computational complexity.
Cite as

Martin Avanzini and Ugo Dal Lago. On Sharing, Memoization, and Polynomial Time. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 62-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{avanzini_et_al:LIPIcs.STACS.2015.62,
  author =	{Avanzini, Martin and Dal Lago, Ugo},
  title =	{{On Sharing, Memoization, and Polynomial Time}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{62--75},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.62},
  URN =		{urn:nbn:de:0030-drops-49042},
  doi =		{10.4230/LIPIcs.STACS.2015.62},
  annote =	{Keywords: implicit computational complexity, data-tiering, polynomial time}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.76
Proof Complexity of Resolution-based QBF Calculi

Authors: Olaf Beyersdorff, Leroy Chew, and Mikolás Janota

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Proof systems for quantified Boolean formulas (QBFs) provide a theoretical underpinning for the performance of important QBF solvers. However, the proof complexity of these proof systems is currently not well understood and in particular lower bound techniques are missing. In this paper we exhibit a new and elegant proof technique for showing lower bounds in QBF proof systems based on strategy extraction. This technique provides a direct transfer of circuit lower bounds to lengths of proofs lower bounds. We use our method to show the hardness of a natural class of parity formulas for Q-resolution and universal Q-resolution. Variants of the formulas are hard for even stronger systems as long-distance Q-resolution and extensions. With a completely different lower bound argument we show the hardness of the prominent formulas of Kleine Büning et al. [34] for the strong expansion-based calculus IR-calc. Our lower bounds imply new exponential separations between two different types of resolution-based QBF calculi: proof systems for CDCL-based solvers (Q-resolution, long-distance Q-resolution) and proof systems for expansion-based solvers (forallExp+Res and its generalizations IR-calc and IRM-calc). The relations between proof systems from the two different classes were not known before.
Cite as

Olaf Beyersdorff, Leroy Chew, and Mikolás Janota. Proof Complexity of Resolution-based QBF Calculi. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 76-89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{beyersdorff_et_al:LIPIcs.STACS.2015.76,
  author =	{Beyersdorff, Olaf and Chew, Leroy and Janota, Mikol\'{a}s},
  title =	{{Proof Complexity of Resolution-based QBF Calculi}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{76--89},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.76},
  URN =		{urn:nbn:de:0030-drops-49057},
  doi =		{10.4230/LIPIcs.STACS.2015.76},
  annote =	{Keywords: proof complexity, QBF, lower bound techniques, separations}
}
  • Refine by Author
  • 11 Mayr, Ernst W.
  • 5 Meyer auf der Heide, Friedhelm
  • 2 Boyar, Joan
  • 2 Bringmann, Karl
  • 2 Cole, Richard
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 5 online algorithms
  • 4 approximation algorithms
  • 4 lower bounds
  • 3 complexity
  • 2 Complexity
  • Show More...

  • Refine by Type
  • 130 document
  • 2 volume

  • Refine by Publication Year
  • 63 2015
  • 61 2014
  • 2 1997
  • 1 1991
  • 1 1992
  • 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