LIPIcs, Volume 30
STACS 2015, March 4-7, 2015, Garching, Germany
Editors: Ernst W. Mayr and Nicolas Ollinger
LIPIcs, Volume 25
STACS 2014, March 5-8, 2014, Lyon, France
Editors: Ernst W. Mayr and Natacha Portier
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Feedback for Dagstuhl Publishing