133 Search Results for "Vall�e, Brigitte"

Document
Invited Talk
DOI: 10.4230/LIPIcs.AofA.2022.1
Building Sources of Zero Entropy: Rescaling and Inserting Delays (Invited Talk)

Authors: Ali Akhavi, Fréderic Paccaut, and Brigitte Vallée

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
Most of the natural sources that intervene in Information Theory have a positive entropy. They are well studied. The paper aims in building, in an explicit way, natural instances of sources with zero entropy. Such instances are obtained by slowing down sources of positive entropy, with processes which rescale sources or insert delays. These two processes - rescaling or inserting delays - are essentially the same; they do not change the fundamental intervals of the source, but only the "depth" at which they will be used, or the "speed" at which they are divided. However, they modify the entropy and lead to sources with zero entropy. The paper begins with a "starting" source of positive entropy, and uses a natural class of rescalings of sublinear type. In this way, it builds a class of sources of zero entropy that will be further analysed. As the starting sources possess well understood probabilistic properties, and as the process of rescaling does not change its fundamental intervals, the new sources keep the memory of some important probabilistic features of the initial source. Thus, these new sources may be thoroughly analysed, and their main probabilistic properties precisely described. We focus in particular on two important questions: exhibiting asymptotical normal behaviours à la Shannon-MacMillan-Breiman; analysing the depth of the tries built on the sources. In each case, we obtain a parameterized class of precise behaviours. The paper deals with the analytic combinatorics methodology and makes a great use of generating series.
Cite as

Ali Akhavi, Fréderic Paccaut, and Brigitte Vallée. Building Sources of Zero Entropy: Rescaling and Inserting Delays (Invited Talk). In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 1:1-1:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{akhavi_et_al:LIPIcs.AofA.2022.1,
  author =	{Akhavi, Ali and Paccaut, Fr\'{e}deric and Vall\'{e}e, Brigitte},
  title =	{{Building Sources of Zero Entropy: Rescaling and Inserting Delays}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{1:1--1:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.1},
  URN =		{urn:nbn:de:0030-drops-160879},
  doi =		{10.4230/LIPIcs.AofA.2022.1},
  annote =	{Keywords: Information Theory, Probabilistic analysis of sources, Sources with zero-entropy, Analytic combinatorics, Dirichlet generating functions, Transfer operator, Trie structure, Continued fraction expansion, Rice method, Quasi-power Theorem}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.4
Two Arithmetical Sources and Their Associated Tries

Authors: Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martín D. Safe, and Brigitte Vallée

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

Abstract
This article is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is "not too large". Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth. The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. In our context, the generating function associated with each source is explicit and related to classical functions in Number Theory, as the ζ function, the double ζ function or the transfer operator associated with the Gauss map. We obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours.
Cite as

Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martín D. Safe, and Brigitte Vallée. Two Arithmetical Sources and Their Associated Tries. 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. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.AofA.2020.4,
  author =	{Berth\'{e}, Val\'{e}rie and Cesaratto, Eda and Paccaut, Fr\'{e}d\'{e}ric and Rotondo, Pablo and Safe, Mart{\'\i}n D. and Vall\'{e}e, Brigitte},
  title =	{{Two Arithmetical Sources and Their Associated Tries}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{4:1--4:19},
  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.4},
  URN =		{urn:nbn:de:0030-drops-120345},
  doi =		{10.4230/LIPIcs.AofA.2020.4},
  annote =	{Keywords: Combinatorics of words, Information Theory, Probabilistic analysis, Analytic combinatorics, Dirichlet generating functions, Sources, Partitions, Trie structure, Continued fraction expansion, Farey map, Sturm words, Transfer operator}
}
Document
DOI: 10.4230/LIPIcs.CPM.2019.19
Dichotomic Selection on Words: A Probabilistic Analysis

Authors: Ali Akhavi, Julien Clément, Dimitri Darthenay, Loïck Lhote, and Brigitte Vallée

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Abstract
The paper studies the behaviour of selection algorithms that are based on dichotomy principles. On the entry formed by an ordered list L and a searched element x not in L, they return the interval of the list L the element x belongs to. We focus here on the case of words, where dichotomy principles lead to a selection algorithm designed by Crochemore, Hancart and Lecroq, which appears to be "quasi-optimal". We perform a probabilistic analysis of this algorithm that exhibits its quasi-optimality on average.
Cite as

Ali Akhavi, Julien Clément, Dimitri Darthenay, Loïck Lhote, and Brigitte Vallée. Dichotomic Selection on Words: A Probabilistic Analysis. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{akhavi_et_al:LIPIcs.CPM.2019.19,
  author =	{Akhavi, Ali and Cl\'{e}ment, Julien and Darthenay, Dimitri and Lhote, Lo\"{i}ck and Vall\'{e}e, Brigitte},
  title =	{{Dichotomic Selection on Words: A Probabilistic Analysis}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.19},
  URN =		{urn:nbn:de:0030-drops-104903},
  doi =		{10.4230/LIPIcs.CPM.2019.19},
  annote =	{Keywords: dichotomic selection, text algorithms, analysis of algorithms, average case analysis of algorithms, trie, suffix array, lcp-array, information theory, numeration process, sources, entropy, coincidence, analytic combinatorics, depoissonization techniques}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2018.19
Index-Stratified Types

Authors: Rohan Jacob-Rao, Brigitte Pientka, and David Thibodeau

Published in: LIPIcs, Volume 108, 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)

Abstract
We present Tores, a core language for encoding metatheoretic proofs. The novel features we introduce are well-founded Mendler-style (co)recursion over indexed data types and a form of recursion over objects in the index language to build new types. The latter, which we call index-stratified types, are analogue to the concept of large elimination in dependently typed languages. These features combined allow us to encode sophisticated case studies such as normalization for lambda calculi and normalization by evaluation. We prove the soundness of Tores as a programming and proof language via the key theorems of subject reduction and termination.
Cite as

Rohan Jacob-Rao, Brigitte Pientka, and David Thibodeau. Index-Stratified Types. In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 108, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jacobrao_et_al:LIPIcs.FSCD.2018.19,
  author =	{Jacob-Rao, Rohan and Pientka, Brigitte and Thibodeau, David},
  title =	{{Index-Stratified Types}},
  booktitle =	{3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-077-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{108},
  editor =	{Kirchner, H\'{e}l\`{e}ne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2018.19},
  URN =		{urn:nbn:de:0030-drops-91891},
  doi =		{10.4230/LIPIcs.FSCD.2018.19},
  annote =	{Keywords: Indexed types, (co)recursive types, logical relations}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.35
The Depoissonisation Quintet: Rice-Poisson-Mellin-Newton-Laplace

Authors: Brigitte Vallée

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
This paper is devoted to the Depoissonisation process which is central in various analyses of the AofA domain. We first recall in Section 1 the two possible paths that may be used in this process, namely the Depoissonisation path and the Rice path. The two paths are rarely described for themselves in the literature, and general methodological results are often difficult to isolate amongst particular results that are more directed towards various applications. The main results for the Depoissonisation path are scattered in at least five papers, with a chronological order which does not correspond to the logical order of the method. The Rice path is also almost always presented with a strong focus towards possible applications. It is often very easy to apply, but it needs a tameness condition, which appears a priori to be quite restrictive, and is not deeply studied in the literature. This explains why the Rice path is very often undervalued. Second, the two paths are not precisely compared, and the situation creates various "feelings": some people see the tools that are used in the two paths as quite different, and strongly prefer one of the two paths; some others think the two paths are almost the same, with just a change of vocabulary. It is thus useful to compare the two paths and the tools they use. This will be done in Sections 2 and 3. We also "follow" this comparison on a precise problem, related to the analysis of tries, introduced in Section 1.7. The paper also exhibits in Section 4 a new framework, of practical use, where the tameness condition of Rice path is proven to hold. This approach, perhaps of independent interest, deals with the shifting of sequences and then the inverse Laplace transform, which does not seem of classical use in this context. It performs very simple computations. This adds a new method to the Depoissonisation context and explains the title of the paper. We then conclude that the Rice path is both of easy and practical use: even though (much?) less general than the Depoissonisation path, it is easier to apply.
Cite as

Brigitte Vallée. The Depoissonisation Quintet: Rice-Poisson-Mellin-Newton-Laplace. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vallee:LIPIcs.AofA.2018.35,
  author =	{Vall\'{e}e, Brigitte},
  title =	{{The Depoissonisation Quintet: Rice-Poisson-Mellin-Newton-Laplace}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.35},
  URN =		{urn:nbn:de:0030-drops-89284},
  doi =		{10.4230/LIPIcs.AofA.2018.35},
  annote =	{Keywords: Analysis of Algorithms, Poisson model, Mellin transform, Rice integral, Laplace transform, Newton interpolation, Depoissonisation, sources, trie structure, algorithms on words}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2018
LIPIcs, Volume 96, STACS'18, Complete Volume

Authors: Rolf Niedermeier and Brigitte Vallée

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
LIPIcs, Volume 96, STACS'18, Complete Volume
Cite as

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

Copy BibTex To Clipboard

@Proceedings{niedermeier_et_al:LIPIcs.STACS.2018,
  title =	{{LIPIcs, Volume 96, STACS'18, Complete Volume}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018},
  URN =		{urn:nbn:de:0030-drops-86179},
  doi =		{10.4230/LIPIcs.STACS.2018},
  annote =	{Keywords: Mathematics of computing, Theory of computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Rolf Niedermeier and Brigitte Vallée

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

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

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

Copy BibTex To Clipboard

@InProceedings{niedermeier_et_al:LIPIcs.STACS.2018.0,
  author =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.0},
  URN =		{urn:nbn:de:0030-drops-84807},
  doi =		{10.4230/LIPIcs.STACS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.1
Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation

Authors: Bruno Salvy

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
In a probabilistic context, the main data structures of computer science are viewed as random combinatorial objects. Analytic Combinatorics, as described in the book by Flajolet and Sedgewick, provides a set of high-level tools for their probabilistic analysis. Recursive combinatorial definitions lead to generating function equations from which efficient algorithms can be designed for enumeration, random generation and, to some extent, asymptotic analysis. With a focus on random generation, this tutorial first covers the basics of Analytic Combinatorics and then describes the idea of Boltzmann sampling and its realisation. The tutorial addresses a broad TCS audience and no particular pre-knowledge on analytic combinatorics is expected.
Cite as

Bruno Salvy. Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{salvy:LIPIcs.STACS.2018.1,
  author =	{Salvy, Bruno},
  title =	{{Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{1:1--1:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.1},
  URN =		{urn:nbn:de:0030-drops-85352},
  doi =		{10.4230/LIPIcs.STACS.2018.1},
  annote =	{Keywords: Analytic Combinatorics, Generating Functions, Random Generation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.2
Lower Bound Techniques for QBF Proof Systems

Authors: Meena Mahajan

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
How do we prove that a false QBF is inded false? How big a proof is needed? The special case when all quantifiers are existential is the well-studied setting of propositional proof complexity. Expectedly, universal quantifiers change the game significantly. Several proof systems have been designed in the last couple of decades to handle QBFs. Lower bound paradigms from propositional proof complexity cannot always be extended - in most cases feasible interpolation and consequent transfer of circuit lower bounds works, but obtaining lower bounds on size by providing lower bounds on width fails dramatically. A new paradigm with no analogue in the propositional world has emerged in the form of strategy extraction, allowing for transfer of circuit lower bounds, as well as obtaining independent genuine QBF lower bounds based on a semantic cost measure. This talk will provide a broad overview of some of these developments.
Cite as

Meena Mahajan. Lower Bound Techniques for QBF Proof Systems. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 2:1-2:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mahajan:LIPIcs.STACS.2018.2,
  author =	{Mahajan, Meena},
  title =	{{Lower Bound Techniques for QBF Proof Systems}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{2:1--2:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.2},
  URN =		{urn:nbn:de:0030-drops-85362},
  doi =		{10.4230/LIPIcs.STACS.2018.2},
  annote =	{Keywords: Proof Complexity, Quantified Boolean formulas, Resolution, Lower Bound Techniques}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.3
On the Positive Calculus of Relations with Transitive Closure

Authors: Damien Pous

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Binary relations are such a basic object that they appear in many places in mathematics and computer science. For instance, when dealing with graphs, program semantics, or termination guarantees, binary relations are always used at some point. In this survey, we focus on the relations themselves, and we consider algebraic and algorithmic questions. On the algebraic side, we want to understand and characterise the laws governing the behaviour of the following standard operations on relations: union, intersection, composition, converse, and reflexive-transitive closure. On the algorithmic side, we look for decision procedures for equality or inequality of relations. After having formally defined the calculus of relations, we recall the existing results about two well-studied fragments of particular importance: Kleene algebras and allegories. Unifying those fragments yields a decidable theory whose axiomatisability remains an open problem.
Cite as

Damien Pous. On the Positive Calculus of Relations with Transitive Closure. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{pous:LIPIcs.STACS.2018.3,
  author =	{Pous, Damien},
  title =	{{On the Positive Calculus of Relations with Transitive Closure}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.3},
  URN =		{urn:nbn:de:0030-drops-85382},
  doi =		{10.4230/LIPIcs.STACS.2018.3},
  annote =	{Keywords: Relation Algebra, Kleene Algebra, Allegories, Automata, Graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.4
The Open Shop Scheduling Problem

Authors: Gerhard J. Woeginger

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
We discuss the computational complexity, the approximability, the algorithmics and the combinatorics of the open shop scheduling problem. We summarize the most important results from the literature and explain their main ideas, we sketch the most beautiful proofs, and we also list a number of open problems.
Cite as

Gerhard J. Woeginger. The Open Shop Scheduling Problem. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{woeginger:LIPIcs.STACS.2018.4,
  author =	{Woeginger, Gerhard J.},
  title =	{{The Open Shop Scheduling Problem}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.4},
  URN =		{urn:nbn:de:0030-drops-85375},
  doi =		{10.4230/LIPIcs.STACS.2018.4},
  annote =	{Keywords: Algorithms, Complexity, Scheduling, Approximation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.5
Approximating Airports and Railways

Authors: Anna Adamaszek, Antonios Antoniadis, Amit Kumar, and Tobias Mömke

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
In this paper we consider the airport and railway problem (AR), which combines capacitated facility location with network design, both in the general metric and the two-dimensional Euclidean space. An instance of the airport and railway problem consists of a set of points in the corresponding metric, together with a non-negative weight for each point, and a parameter k. The points represent cities, the weights denote costs of opening an airport in the corresponding city, and the parameter k is a maximum capacity of an airport. The goal is to construct a minimum cost network of airports and railways connecting all the cities, where railways correspond to edges connecting pairs of points, and the cost of a railway is equal to the distance between the corresponding points. The network is partitioned into components, where each component contains an open airport, and spans at most k cities. For the Euclidean case, any points in the plane can be used as Steiner vertices of the network. We obtain the first bicriteria approximation algorithm for AR for the general metric case, which yields a 4-approximate solution with a resource augmentation of the airport capacity k by a factor of 2. More generally, for any parameter 0 < p <= 1 where pk is an integer we develop a (4/3)(2 + 1/p)-approximation algorithm for metric AR with a resource augmentation by a factor of 1 + p. Furthermore, we obtain the first constant factor approximation algorithm that does not resort to resource augmentation for AR in the Euclidean plane. Additionally, for the Euclidean setting we provide a quasi-polynomial time approximation scheme for the same problem with a resource augmentation by a factor of 1 + mu on the airport capacity, for any fixed mu > 0.
Cite as

Anna Adamaszek, Antonios Antoniadis, Amit Kumar, and Tobias Mömke. Approximating Airports and Railways. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.STACS.2018.5,
  author =	{Adamaszek, Anna and Antoniadis, Antonios and Kumar, Amit and M\"{o}mke, Tobias},
  title =	{{Approximating Airports and Railways}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.5},
  URN =		{urn:nbn:de:0030-drops-85183},
  doi =		{10.4230/LIPIcs.STACS.2018.5},
  annote =	{Keywords: Network Design, Facility Location, Approximation Algorithms, PTAS, Metric, Euclidean}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.6
Property Testing for Bounded Degree Databases

Authors: Isolde Adler and Frederik Harwath

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Aiming at extremely efficient algorithms for big data sets, we introduce property testing of relational databases of bounded degree. Our model generalises the bounded degree model for graphs (Goldreich and Ron, STOC 1997). We prove that in this model, if the databases have bounded tree-width, then every query definable in monadic second-order logic with modulo counting is testable with a constant number of oracle queries and polylogarithmic running time. This is the first logical meta-theorem in property testing of sparse models. Furthermore, we discuss conditions for the existence of uniform and non-uniform testers.
Cite as

Isolde Adler and Frederik Harwath. Property Testing for Bounded Degree Databases. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{adler_et_al:LIPIcs.STACS.2018.6,
  author =	{Adler, Isolde and Harwath, Frederik},
  title =	{{Property Testing for Bounded Degree Databases}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.6},
  URN =		{urn:nbn:de:0030-drops-85288},
  doi =		{10.4230/LIPIcs.STACS.2018.6},
  annote =	{Keywords: logic and databases, property testing, logical meta-theorems, bounded degree model, sublinear algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.7
Erdös-Pósa Property of Obstructions to Interval Graphs

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

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
The duality between packing and covering problems lies at the heart of fundamental combinatorial proofs, as well as well-known algorithmic methods such as the primal-dual method for approximation and win/win-approach for parameterized analysis. The very essence of this duality is encompassed by a well-known property called the Erdös-Pósa property, which has been extensively studied for over five decades. Informally, we say that a class of graphs F admits the Erdös-Pósa property if there exists f such that for any graph G, either G has vertex-disjoint "copies" of the graphs in F, or there is a set S \subseteq V(G) of f(k) vertices that intersects all copies of the graphs in F. In the context of any graph class G, the most natural question that arises in this regard is as follows - do obstructions to G have the Erdös-Pósa property? Having this view in mind, we focus on the class of interval graphs. Structural properties of interval graphs are intensively studied, also as they lead to the design of polynomial-time algorithms for classic problems that are NP-hard on general graphs. Nevertheless, about one of the most basic properties of such graphs, namely, the Erdös-Pósa property, nothing is known. In this paper, we settle this anomaly: we prove that the family of obstructions to interval graphs - namely, the family of chordless cycles and ATs---admits the Erdös-Pósa property. Our main theorem immediately results in an algorithm to decide whether an input graph G has vertex-disjoint ATs and chordless cycles, or there exists a set of O(k^2 log k) vertices in G that hits all ATs and chordless cycles.
Cite as

Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Erdös-Pósa Property of Obstructions to Interval Graphs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.STACS.2018.7,
  author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Misra, Pranabendu and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Erd\"{o}s-P\'{o}sa Property of Obstructions to Interval Graphs}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.7},
  URN =		{urn:nbn:de:0030-drops-84815},
  doi =		{10.4230/LIPIcs.STACS.2018.7},
  annote =	{Keywords: Interval Graphs, Obstructions, Erd\"{o}s-P\'{o}sa Property}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.8
All Classical Adversary Methods are Equivalent for Total Functions

Authors: Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity fbs(f). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. For partial functions, we show unbounded separations between fbs(f) and other adversary bounds, as well as between the relational and Kolmogorov complexity bounds. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than sqrt(n * bs(f)), where n is the number of variables and bs(f) is the block sensitivity. Then we exhibit a partial function f that matches this upper bound, fbs(f) = Omega(sqrt(n * bs(f))).
Cite as

Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs. All Classical Adversary Methods are Equivalent for Total Functions. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.STACS.2018.8,
  author =	{Ambainis, Andris and Kokainis, Martins and Prusis, Krisjanis and Vihrovs, Jevgenijs},
  title =	{{All Classical Adversary Methods are Equivalent for Total Functions}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.8},
  URN =		{urn:nbn:de:0030-drops-84953},
  doi =		{10.4230/LIPIcs.STACS.2018.8},
  annote =	{Keywords: Randomized Query Complexity, Lower Bounds, Adversary Bounds, Fractional Block Sensitivity}
}
  • Refine by Author
  • 8 Vallée, Brigitte
  • 4 Lohrey, Markus
  • 3 Ganardi, Moses
  • 3 Ganian, Robert
  • 3 König, Daniel
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Pattern matching
  • 3 Theory of computation → Randomness, geometry and discrete structures
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 4 lower bounds
  • 3 Approximation Algorithms
  • 3 Constraint Satisfaction
  • 3 Lower Bounds
  • 3 Parameterized Complexity
  • Show More...

  • Refine by Type
  • 133 document

  • Refine by Publication Year
  • 62 2018
  • 60 2017
  • 6 2016
  • 1 2009
  • 1 2013
  • 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