Volume
LIPIcs, Volume 24
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Event
FSTTCS 2013, December 12-14, 2013, Guwahati, IndiaEditors
Publication Details
- published at: 2013-12-10
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-939897-64-4
- DBLP: db/conf/fsttcs/fsttcs2013
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 24, FSTTCS'13, Complete Volume
Abstract
LIPIcs, Volume 24, FSTTCS'13, Complete Volume
Cite as
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
Copy BibTex To Clipboard
@Proceedings{seth_et_al:LIPIcs.FSTTCS.2013,
title = {{LIPIcs, Volume 24, FSTTCS'13, Complete Volume}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2014},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013},
URN = {urn:nbn:de:0030-drops-44358},
doi = {10.4230/LIPIcs.FSTTCS.2013},
annote = {Keywords: Software/Program Verification, Models of Computation, Modes of Computation, Complexity Measures and Classes, Nonnumerical Algorithms and Problems, Spe Programs, Mathematical Logic, Formal Languages}
}
Document
Front Matter
Frontmatter, Table of Contents, Preface, Conference Organization
Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{seth_et_al:LIPIcs.FSTTCS.2013.i,
author = {Seth, Anil and Vishnoi, Nisheeth K.},
title = {{Frontmatter, Table of Contents, Preface, Conference Organization}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {i--xiv},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.i},
URN = {urn:nbn:de:0030-drops-44041},
doi = {10.4230/LIPIcs.FSTTCS.2013.i},
annote = {Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk)
Abstract
Shannon's monumental 1948 work laid the foundations for the rich fields of information and coding theory. The quest for efficient coding schemes to approach Shannon capacity has occupied researchers ever since, with spectacular progress enabling the widespread use of error-correcting codes in practice. Yet the theoretical problem of approaching capacity arbitrarily closely with polynomial complexity remained open except in the special case of erasure channels.
In 2008, Arikan proposed an insightful new method for constructing capacity-achieving codes based on channel polarization. In this talk, I will begin with a self-contained survey of Arikan's celebrated construction of polar codes, and then discuss our recent proof (with Patrick Xia) that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within epsilon > 0 of the Shannon capacity with block length (delay), construction complexity, and decoding complexity all bounded by a polynomial in the gap to capacity, i.e., by poly(1/epsilon). Polar coding gives the first explicit construction with rigorous proofs of all these properties; previous constructions were not known to achieve capacity with less than exp(1/epsilon) decoding complexity.
We establish the capacity-achieving property of polar codes via a direct analysis of the underlying martingale of conditional entropies, without relying on the martingale convergence theorem. This step gives rough polarization (noise levels epsilon for the good channels), which can then be adequately amplified by tracking the decay of the channel Bhattacharyya parameters. Our effective bounds imply that polar codes can have block length bounded by
poly(1/epsilon). We also show that the generator matrix of such polar codes can be constructed in polynomial time by algorithmically computing an adequate approximation of the polarization process.
Cite as
Venkatesan Guruswami. Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{guruswami:LIPIcs.FSTTCS.2013.1,
author = {Guruswami, Venkatesan},
title = {{Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {1--1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.1},
URN = {urn:nbn:de:0030-drops-43992},
doi = {10.4230/LIPIcs.FSTTCS.2013.1},
annote = {Keywords: Error-correction algorithms, Linear Codes, Shannon capacity, Martingale convergence, Computational complexity}
}
Document
Invited Talk
Computing With a Fixed Number of Pointers (Invited Talk)
Abstract
Consider the P-complete problem Horn which asks whether a given set of Horn clauses is (un)satisfiable. To solve it one keeps a dynamic set of atoms that are forced to be true. Using the clauses one then adds atoms to this set until saturation is reached. It is easy to see that this dynamic set will in general more than constant size even if we allow to discard already proved atoms. Given that we need logarithmic space to store a single atom on a Turing machine tape this seems like a strong intuitive argument for the hypothesis that logarithmic space is different from polynomial time. We thus tried to find formal models of computation in which this intuitive argument can be made rigorous. Thus, we study computational models that can be simulated in logarithmic space and encompass logspace algorithms which manipulate a constant size of objects that require logarithmic space individually such as pointers or graph nodes. The hope is then to be able to show that such models are provably unable to solve P-complete problems. We report in this survey article on our partial results towards this goal as well as the state-of-the-art in general.
Cite as
Martin Hofmann and Ramyaa Ramyaa. Computing With a Fixed Number of Pointers (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 3-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{hofmann_et_al:LIPIcs.FSTTCS.2013.3,
author = {Hofmann, Martin and Ramyaa, Ramyaa},
title = {{Computing With a Fixed Number of Pointers}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {3--18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.3},
URN = {urn:nbn:de:0030-drops-44009},
doi = {10.4230/LIPIcs.FSTTCS.2013.3},
annote = {Keywords: Logarithmic space, Jumping graph automata, st-connectivity, co-st-connectivity, Cayley graphs}
}
Document
Invited Talk
On Approximation Resistance of Predicates (Invited Talk)
Abstract
Constraint satisfaction problems are some of the most well-studied NP-hard problems, 3SAT being a prominent example. It is known by Hastad's 1997 result that 3SAT is "approximation resistant" in the following sense: given a near-satisfiable instance, a trivial algorithm that assigns random boolean values to the variables satisfies 7/8 fraction of the constraints and no efficient algorithm can do strictly better unless P=NP!
3SAT is a CSP that corresponds to the ternary OR predicate. In general, a CSP has constraints given by some fixed predicate P:{0,1}^k -> {True, False} (on possibly negated variables) and the predicate is called approximation resistant if, on a near-satisfiable instance, it is computationally hard to perform strictly better than a random assignment.
The quest to understand approximation resistance has played a central role in the theory of probabilistically checkable proofs (PCPs) and hardness of approximation. This talk will give a survey of the topic, including recent work giving a complete characterization of approximation resistance (i.e. a necessary and sufficient condition on the predicate that makes the corresponding CSP approximation resistant).
Cite as
Subhash Khot. On Approximation Resistance of Predicates (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, p. 19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{khot:LIPIcs.FSTTCS.2013.19,
author = {Khot, Subhash},
title = {{On Approximation Resistance of Predicates}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {19--19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.19},
URN = {urn:nbn:de:0030-drops-44011},
doi = {10.4230/LIPIcs.FSTTCS.2013.19},
annote = {Keywords: Approximation resistance, Hardness of approximation, Probabilistically checkable proofs, Constraint satisfaction problem}
}
Document
Invited Talk
Characterisations of Nowhere Dense Graphs (Invited Talk)
Abstract
Nowhere dense classes of graphs were introduced by Nesetril and Ossona de Mendez as a model for "sparsity" in graphs. It turns out that nowhere dense classes of graphs can be characterised in many different ways and have been shown to be equivalent to other concepts studied in areas such as (finite) model theory. Therefore, the concept of nowhere density seems to capture a natural property of graph classes generalising for example classes of graphs which exclude a fixed minor, have bounded degree or bounded local tree-width. In this paper we give a self-contained introduction to the concept of nowhere dense classes of graphs focussing on the various ways in which they can be characterised. We also briefly sketch algorithmic applications these characterisations have found in the literature.
Cite as
Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Characterisations of Nowhere Dense Graphs (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 21-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{grohe_et_al:LIPIcs.FSTTCS.2013.21,
author = {Grohe, Martin and Kreutzer, Stephan and Siebertz, Sebastian},
title = {{Characterisations of Nowhere Dense Graphs}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {21--40},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.21},
URN = {urn:nbn:de:0030-drops-44029},
doi = {10.4230/LIPIcs.FSTTCS.2013.21},
annote = {Keywords: Graph Algorithms, Algorithmic Graph Structure Theory, Finite Model Theory, Nowhere Dense Classes of Graphs}
}
Document
Invited Talk
Intersection Types for Normalization and Verification (Invited Talk)
Abstract
One of the basic principles in typed lambda calculi is that
typable lambda terms are normalizable. Since the converse direction does not hold for simply typed lambda calculus, people have been studying its extensions. This gave birth to the intersection type systems, that exactly characterize various classes
of lambda terms, such as strongly/weakly normalizable terms and
solvable ones (see e.g. [van Bakel/TCS/1995] for a survey).
More recently, a new trend has emerged: intersection types are
not only useful for extending simple types but also for refining them
[Salvati/JoLLI/2010]. One thus obtains finer information on simply typed terms by assigning intersection types. This in particular leads to the concept of normalization by typing, that turns out to be quite efficient in some situations [Terui/RTA/2012]. Moreover, intersection types are invariant under beta-equivalence, so that they constitute a denotational semantics in a natural way [Ehrhard/CSL/2012].
Finally, intersection types also work in an infinitary setting,where terms may represent infinite trees and types play the role of automata. This leads to a model checking framework for higher order recursion schemes via intersection types [Kobayashi/POPL/2009, Kobayashi+Luke Ong/LICS/2009].
The purpose of this talk is to outline the recent development of intersection types described above. In particular, we explain how an efficient evaluation algorithm is obtained by combining normalization by typing, beta-reduction and Krivine's abstract machine, to result in the following complexity characterization. Consider simply typed lambda terms of boolean type o -> o -> o and of order r. Then the problem of deciding whether a given term evaluates to "true" is
complete for n-EXPTIME if r = 2n +2, and complete for n- EXPSPACE
if r = 2n + 3 [Terui/RTA/2012].
Cite as
Kazushige Terui. Intersection Types for Normalization and Verification (Invited Talk). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 41-42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{terui:LIPIcs.FSTTCS.2013.41,
author = {Terui, Kazushige},
title = {{Intersection Types for Normalization and Verification}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {41--42},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.41},
URN = {urn:nbn:de:0030-drops-44032},
doi = {10.4230/LIPIcs.FSTTCS.2013.41},
annote = {Keywords: simply typed lambda calculus, computational complexity, denotational semantics, intersection types}
}
Document
Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound
Abstract
Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of
lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<lambda<1 and
lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda*m+(1-lambda)(n-1)/2 edges. The property of being bipartite is
lambda-extendible for lambda =1/2, and so the Poljak-Turzik bound
generalizes the well-known Edwards-Erdos bound for Max Cut. Other examples of lambda-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some q in N.
Mnich et al. (FSTTCS 2012) defined the closely related notion of strong lambda-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly lambda-extendible property Pi is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound---does there exist a spanning subgraph H of a connected graph G such that H in Pi and H has at least lambda*m+(1-lambda)(n-1)/2+k edges?---subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. This generalized an earlier result of Crowston et al. (ICALP 2012) for Max Cut, to all strongly lambda-extendible properties which satisfy the additional criterion.
In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when lambda=1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.
Cite as
Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 43-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{crowston_et_al:LIPIcs.FSTTCS.2013.43,
author = {Crowston, Robert and Jones, Mark and Muciaccia, Gabriele and Philip, Geevarghese and Rai, Ashutosh and Saurabh, Saket},
title = {{Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {43--54},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.43},
URN = {urn:nbn:de:0030-drops-43599},
doi = {10.4230/LIPIcs.FSTTCS.2013.43},
annote = {Keywords: Kernelization, Lambda Extension, Above-Guarantee Parameterization, MaxCut}
}
Document
On the Parameterised Complexity of String Morphism Problems
Abstract
Given a source string u and a target string w, to decide whether w can be obtained by applying a string morphism on u (i. e., uniformly
replacing the symbols in u by strings) constitutes an NP-complete
problem. For example, the target string w := baaba can be obtained from the source string u := aba, by replacing a and b in u by the strings ba and a, respectively. In this paper, we contribute to the recently started investigation of the computational complexity of the string morphism problem by studying it in the framework of parameterised complexity.
Cite as
Henning Fernau, Markus L. Schmid, and Yngve Villanger. On the Parameterised Complexity of String Morphism Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 55-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{fernau_et_al:LIPIcs.FSTTCS.2013.55,
author = {Fernau, Henning and Schmid, Markus L. and Villanger, Yngve},
title = {{On the Parameterised Complexity of String Morphism Problems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {55--66},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.55},
URN = {urn:nbn:de:0030-drops-43619},
doi = {10.4230/LIPIcs.FSTTCS.2013.55},
annote = {Keywords: String Problems, String Morphisms, Parameterised Complexity, Exponential Time Hypothesis, Pattern Languages}
}
Document
Partially Polynomial Kernels for Set Cover and Test Cover
Abstract
In a typical covering problem we are given a universe U of size n, a family S (S could be given implicitly) of size m and an integer k and the objective is to check whether there exists a subfamily S' \subseteq S of size at most k satisfying some desired properties. If S' is required to contain all the elements of U then it corresponds to the classical Set Cover problem. On the other hand if we require S' to satisfy the property that for every pair of elements x,y \in U there exists a set S \in S' such that |S \cap {x,y}|=1 then it corresponds to the Test Cover problem. In this paper we consider a natural parameterization of Set Cover and Test Cover. More precisely, we study the (n-k)-Set Cover and (n-k)-Test Cover problems, where the objective is to find a subfamily S' of size at most n-k satisfying the respective properties, from the kernelization perspective. It is known in the literature that both (n-k)-Set Cover and (n-k)-Test Cover do not admit polynomial kernels (under some well known complexity theoretic assumptions). However, in this paper we show that they do admit "partially polynomial kernels". More precisely, we give polynomial time algorithms that take as input an instance (U,S,k) of (n-k)-Set Cover (n-k)-Test Cover) and return an equivalent instance (~U,~S,~k) of (n-k)-Set Cover (respectively (n-k)-Test Cover) with ~k <= k and |~U|= O(k^2) (|~U|=O(k^7)). These results allow us to generalize, improve and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain "sparsity properties". Using a part of our kernelization algorithm for (n-k)-Set Cover, we also get an improved FPT algorithm for this problem which runs in time O(4^k*k^{\O(1)}*(m+n)) improving over the previous best of O(8^{k+o(k)}*(m+n)^{O(1)}). On the other hand the partially polynomial kernel for (n-k)-Test Cover implies the first single exponential FPT algorithm, an algorithm with running time O(2^{O(k^2)}*(m+n)^{O(1)}). We believe such an approach will also be useful for other covering problems as well.
Cite as
Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh. Partially Polynomial Kernels for Set Cover and Test Cover. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 67-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{basavaraju_et_al:LIPIcs.FSTTCS.2013.67,
author = {Basavaraju, Manu and Francis, Mathew C. and Ramanujan, M. S. and Saurabh, Saket},
title = {{Partially Polynomial Kernels for Set Cover and Test Cover}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {67--78},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.67},
URN = {urn:nbn:de:0030-drops-43621},
doi = {10.4230/LIPIcs.FSTTCS.2013.67},
annote = {Keywords: Set Cover, Test Cover, Kernelization, Parameterized Algorithms}
}
Document
Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
Abstract
We consider the Directed Anchored k-Core problem, where the task is for a given directed graph G and integers b, k and p, to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (the anchors) of H have in-degree at least k. For undirected graphs, this problem was introduced by Bhawalkar, Kleinberg, Lewi, Roughgarden, and Sharma [ICALP 2012]. We undertake a
systematic analysis of the computational complexity of Directed Anchored k-Core and show that:
- The decision version of the problem is NP-complete for every k>=1 even if the input graph is restricted to be a planar directed acyclic graph of maximum degree at most k+2.
- The problem is fixed parameter tractable (FPT) parameterized by the size of the core p for k=1, and W[1]-hard for k>=2.
- When the maximum degree of the graph is at most Delta, the problem is FPT parameterized by p+Delta if k>=Delta/2.
Cite as
Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 79-90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{chitnis_et_al:LIPIcs.FSTTCS.2013.79,
author = {Chitnis, Rajesh and Fomin, Fedor V. and Golovach, Petr A.},
title = {{Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {79--90},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.79},
URN = {urn:nbn:de:0030-drops-43636},
doi = {10.4230/LIPIcs.FSTTCS.2013.79},
annote = {Keywords: Parameterized complexity, directed graphs, anchored \$k\$-core}
}
Document
Böhm Trees as Higher-Order Recursive Schemes
Abstract
Higher-order recursive schemes (HORS) are schematic representations of functional programs. They generate possibly infinite ranked labelled trees and, in that respect, are known to be equivalent to a restricted fragment of the lambda-Y-calculus consisting of ground-type terms whose free variables have types of the form o -> ... -> o (with o being a special case).
In this paper, we show that any lambda-Y-term (with no restrictions on term type or the types of free variables) can actually be represented by a HORS. More precisely, for any lambda-Y-term M, there exists a HORS generating a tree that faithfully represents M's (eta-long) Böhm tree. In particular, the HORS captures higher-order binding information contained in the Böhm tree. An analogous result holds for finitary PCF.
As a consequence, we can reduce a variety of problems related to the
lambda-Y-calculus or finitary PCF to problems concerning higher-order
recursive schemes. For instance, Böhm tree equivalence can be reduced
to the equivalence problem for HORS. Our results also enable MSO
model-checking of Böhm trees, despite the general undecidability of
the problem.
Cite as
Pierre Clairambault and Andrzej S. Murawski. Böhm Trees as Higher-Order Recursive Schemes. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 91-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{clairambault_et_al:LIPIcs.FSTTCS.2013.91,
author = {Clairambault, Pierre and Murawski, Andrzej S.},
title = {{B\"{o}hm Trees as Higher-Order Recursive Schemes}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {91--102},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.91},
URN = {urn:nbn:de:0030-drops-43644},
doi = {10.4230/LIPIcs.FSTTCS.2013.91},
annote = {Keywords: Lambda calculus, B\"{o}hm trees, Recursion Schemes}
}
Document
Evaluation is MSOL-compatible
Abstract
We consider simply-typed lambda calculus with fixpoint operators.
Evaluation of a term gives as a result the Böhm tree of the term.
We show that evaluation is compatible with monadic second-order logic (MSOL). This means that for a fixed finite vocabulary of terms, the MSOL properties of Böhm trees of terms are effectively MSOL properties of terms themselves. Theorems of this kind have been known for some graph operations: unfolding, and Muchnik iteration. Similarly to those results, our main theorem has diverse applications. It can be used to show decidability results, to construct classes of graphs with decidable MSOL theory, or to obtain MSOL formulas expressing behavioral properties of terms. Another application is decidability of a control-flow synthesis problem.
Cite as
Sylvain Salvati and Igor Walukiewicz. Evaluation is MSOL-compatible. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 103-114, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{salvati_et_al:LIPIcs.FSTTCS.2013.103,
author = {Salvati, Sylvain and Walukiewicz, Igor},
title = {{Evaluation is MSOL-compatible}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {103--114},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.103},
URN = {urn:nbn:de:0030-drops-43652},
doi = {10.4230/LIPIcs.FSTTCS.2013.103},
annote = {Keywords: Simply typed \$lambda Y\$-calculus; Monadic second order}
}
Document
Model Checking and Functional Program Transformations
Abstract
We study a model for recursive functional programs called higher order recursion schemes (HORS). We give new proofs of two verification related problems: reflection and selection for HORS. The previous proofs are based on the equivalence between HORS and collapsible pushdown automata and they lose the structure of the initial program. The constructions presented here are based on shape preserving transformations, and can be applied on actual programs without losing the structure of the program.
Cite as
Axel Haddad. Model Checking and Functional Program Transformations. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 115-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{haddad:LIPIcs.FSTTCS.2013.115,
author = {Haddad, Axel},
title = {{Model Checking and Functional Program Transformations}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {115--126},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.115},
URN = {urn:nbn:de:0030-drops-43605},
doi = {10.4230/LIPIcs.FSTTCS.2013.115},
annote = {Keywords: Higher-order recursion schemes, Model checking, Tree automata}
}
Document
A Theory of Partitioned Global Address Spaces
Abstract
Partitioned global address space (PGAS) is a parallel programming model for the development of high-performance applications on clusters. It provides a global address space partitioned among the cluster nodes, and is supported in programming languages like C, C++, and Fortran by means of APIs. Our first contribution is a formal model for the semantics of single program, multiple data programs that use PGAS APIs. Our model reflects the main features of popular real-world APIs such as SHMEM, ARMCI, GASNet, GPI, and GASPI.
A key feature of PGAS is the support for one-sided communication: a node may directly read and write the memory located at a remote node, without explicit synchronization with the processes running on the remote side. One-sided communication increases performance by decoupling process synchronization from data transfer, but requires the programmer to reason about appropriate synchronizations between reads and writes. As a second contribution, we propose and investigate robustness, a criterion for correct synchronization of PGAS programs. Robustness corresponds to acyclicity of a suitable happens-before relation defined on PGAS computations. The requirement is finer than classical data race freedom and rules out most false error reports.
Our main technical result is an algorithm for checking robustness of PGAS programs. The algorithm makes use of two insights. We first show that, if a PGAS program is not robust, then there are computations in a certain normal form that violate happens-before acyclicity. Intuitively, normal-form computations delay remote accesses in an ordered way. We then devise an algorithm that checks for cyclic normal-form computations. Essentially, the algorithm is an emptiness check for a novel automaton model that accepts normal-form computations in streaming fashion. Altogether, we prove that the robustness problem is PSPACE complete.
Cite as
Georgel Calin, Egor Derevenetc, Rupak Majumdar, and Roland Meyer. A Theory of Partitioned Global Address Spaces. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 127-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{calin_et_al:LIPIcs.FSTTCS.2013.127,
author = {Calin, Georgel and Derevenetc, Egor and Majumdar, Rupak and Meyer, Roland},
title = {{A Theory of Partitioned Global Address Spaces}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {127--139},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.127},
URN = {urn:nbn:de:0030-drops-43665},
doi = {10.4230/LIPIcs.FSTTCS.2013.127},
annote = {Keywords: PGAS, SC preservation, Robustness, Semantics, Formal languages}
}
Document
A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound
Abstract
The main result of this paper is an optimal strong direct
product result for the two-party public-coin randomized communication
complexity of the Tribes function. This is proved by providing an
alternate proof of the optimal lower bound of Omega(n) for the randomised communication complexity of the Tribes function using the so-called smooth-rectangle bound, introduced by Jain and Klauck [CCC/2010]. The optimal Omega(n) lower bound for Tribes was originally proved by Jayram, Kumar and Sivakumar [STOC/2003], using a more powerful lower bound technique, namely the information complexity bound. The information complexity bound is known to be at least as strong a lower bound method as the smooth-rectangle bound [Kerenidis et al, 2012]. On the other hand, we are not aware of any function or relation for which the smooth-rectangle bound is (asymptotically) smaller than its public-coin randomized communication complexity. The optimal direct product for Tribes is obtained by combining our smooth-rectangle bound for tribes with the strong direct product result of Jain and Yao (2012) in terms of smooth-rectangle bound.
Cite as
Prahladh Harsha and Rahul Jain. A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 141-152, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{harsha_et_al:LIPIcs.FSTTCS.2013.141,
author = {Harsha, Prahladh and Jain, Rahul},
title = {{A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {141--152},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.141},
URN = {urn:nbn:de:0030-drops-43670},
doi = {10.4230/LIPIcs.FSTTCS.2013.141},
annote = {Keywords: Rectangle bound, Tribes function, Strong direct product}
}
Document
Inapproximability of Rainbow Colouring
Abstract
A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one path in which no two edges are coloured the same. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Chakraborty, Fischer, Matsliah and Yuster have shown that it is NP-hard to compute the rainbow connection number of graphs [J. Comb. Optim., 2011]. Basavaraju, Chandran, Rajendraprasad and Ramaswamy have reported an (r+3)-factor approximation algorithm to rainbow colour any graph of radius r [Graphs and Combinatorics, 2012]. In this article, we use a result of Guruswami, Håstad and Sudan on the NP-hardness of colouring a 2-colourable 4-uniform hypergraph using constantly many
colours [SIAM J. Comput., 2002] to show that for every positive integer k, it is NP-hard to distinguish between graphs with rainbow connection number 2k+2 and 4k+2. This, in turn, implies that there cannot exist a polynomial time algorithm to rainbow colour graphs with less than twice the optimum number of colours, unless P=NP.
The authors have earlier shown that the rainbow connection number problem remains NP-hard even when restricted to the class of chordal graphs, though in this case a 4-factor approximation algorithm is available [COCOON, 2012]. In this article, we improve upon the 4-factor approximation algorithm to design a linear-time algorithm that can rainbow colour a chordal graph G using at most 3/2 times the minimum number of colours if G is bridgeless and at most 5/2 times the minimum number of colours otherwise. Finally we show that the rainbow connection number of bridgeless chordal graphs cannot be polynomial-time approximated to a factor less than 5/4, unless P=NP.
Cite as
L. Sunil Chandran and Deepak Rajendraprasad. Inapproximability of Rainbow Colouring. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 153-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{chandran_et_al:LIPIcs.FSTTCS.2013.153,
author = {Chandran, L. Sunil and Rajendraprasad, Deepak},
title = {{Inapproximability of Rainbow Colouring}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {153--162},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.153},
URN = {urn:nbn:de:0030-drops-43689},
doi = {10.4230/LIPIcs.FSTTCS.2013.153},
annote = {Keywords: rainbow connectivity, rainbow colouring, approximation hardness}
}
Document
Primal Infon Logic: Derivability in Polynomial Time
Abstract
Primal infon logic (PIL), introduced by Gurevich and Neeman in 2009, is a logic for authorization in distributed systems. It is a variant of the (and, implies)-fragment of intuitionistic modal logic. It presents many interesting technical challenges -- one of them is to determine the complexity of the derivability problem. Previously, some restrictions of propositional PIL were proved to have a linear time algorithm, and some extensions have been proved to be PSPACE-complete. In this paper, we provide an O(N^3) algorithm for derivability in propositional PIL. The solution involves an interesting interplay between the sequent calculus formulation (to prove the subformula property) and the natural deduction formulation of the logic (based on which we provide an algorithm for the derivability problem).
Cite as
Anguraj Baskar, Prasad Naldurg, K. R. Raghavendra, and S. P. Suresh. Primal Infon Logic: Derivability in Polynomial Time. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 163-174, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{baskar_et_al:LIPIcs.FSTTCS.2013.163,
author = {Baskar, Anguraj and Naldurg, Prasad and Raghavendra, K. R. and Suresh, S. P.},
title = {{Primal Infon Logic: Derivability in Polynomial Time}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {163--174},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.163},
URN = {urn:nbn:de:0030-drops-43708},
doi = {10.4230/LIPIcs.FSTTCS.2013.163},
annote = {Keywords: Authorization logics, Intuitionistic modal logic, Proof theory, Cut elimination, Subformula property}
}
Document
Composition Problems for Braids
Abstract
In this paper we investigate the decidability and complexity
of problems related to braid composition. While all known problems for a class of braids with 3 strands, B_3, have polynomial time solutions we prove that a very natural question for braid composition, the membership problem, is NP-hard for braids with only 3 strands. The membership problem is decidable for B_3, but it becomes harder for a class of braids with more strands. In particular we show that fundamental problems about braid compositions are undecidable for braids with at least 5 strands, but decidability of these problems for B_4 remains open. The paper introduces a few challenging algorithmic problems about topological braids opening new connections between braid groups, combinatorics on words, complexity theory and provides solutions for some of these problems by application of several techniques from automata theory, matrix semigroups and algorithms.
Cite as
Igor Potapov. Composition Problems for Braids. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 175-187, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{potapov:LIPIcs.FSTTCS.2013.175,
author = {Potapov, Igor},
title = {{Composition Problems for Braids}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {175--187},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.175},
URN = {urn:nbn:de:0030-drops-43711},
doi = {10.4230/LIPIcs.FSTTCS.2013.175},
annote = {Keywords: Braid group, automata, group alphabet, combinatorics on words, matrix semigroups, NP-hardness, decidability}
}
Document
DLOGTIME Proof Systems
Abstract
We define DLOGTIME proof systems, DLTPS, which generalize NC0 proof systems. It is known that functions such as Exact_k and Majority do not have NC0 proof systems. Here, we give a DLTPS for Exact_k (and therefore for Majority) and also for other natural functions such as Reach and Cliquek. Though many interesting functions have DLTPS, we show that there are languages in NP which do not have DLTPS.
We consider the closure properties of DLTPS and prove that they are closed under union and concatenation but are not closed under intersection and complement. Finally, we consider a hierarchy of polylogarithmic time proof systems and show that the hierarchy is strict.
Cite as
Andreas Krebs and Nutan Limaye. DLOGTIME Proof Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 189-200, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{krebs_et_al:LIPIcs.FSTTCS.2013.189,
author = {Krebs, Andreas and Limaye, Nutan},
title = {{DLOGTIME Proof Systems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {189--200},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.189},
URN = {urn:nbn:de:0030-drops-43725},
doi = {10.4230/LIPIcs.FSTTCS.2013.189},
annote = {Keywords: Proof systems, DLOGTIME, NC0}
}
Document
On Improved Degree Lower Bounds for Polynomial Approximation
Abstract
A polynomial P in F[X_1,...,X_n] is said to epsilon-approximate a
boolean function F:{0,1}^n -> {0,1} under distribution D over {0,1}^n
if for a random x chosen according to distribution D, the probability
that P(x) is not equal to F(x) is at most epsilon. Smolensky (1987)
showed that for any constant distinct primes p and q, any polynomial P
in F_p[x_1,...,x_n] that (1/2q - Omega(1))-approximates the boolean
function MOD_q:{0,1}^n->{0,1} -- which accepts its input iff the
number of ones is non-zero modulo q -- under the uniform distribution
must have degree Omega(n^{1/2}).
We consider the problem of finding an explicit function
f:{0,1}^n->{0,1} that has no epsilon-approximating polynomial of
degree less than n^{1/2 + Omega(1)} under *some distribution*, for
some constant epsilon>0. We show a number of negative results in this
direction: specifically, we show that many interesting classes of
functions including symmetric functions and linear threshold functions
do have approximating polynomials of degree O(n^{1/2+o(1)}) under
every distribution. This demonstrates the power of this model of
computation.
The above results, in turn, provide further motivation for this lower
bound question. Using the upper bounds obtained above, we show that
finding such a function f would have applications to: lower bounds for
AC^0 o F where F is the class of symmetric and threshold gates;
stronger lower bounds for 1-round compression by ACC^0[p] circuits;
improved correlation lower bounds against low degree polynomials; and
(under further conditions) showing that the Inner Product (over F_2)
function does not have small AC^0 o MOD_2 circuits.
Cite as
Srikanth Srinivasan. On Improved Degree Lower Bounds for Polynomial Approximation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 201-212, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{srinivasan:LIPIcs.FSTTCS.2013.201,
author = {Srinivasan, Srikanth},
title = {{On Improved Degree Lower Bounds for Polynomial Approximation}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {201--212},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.201},
URN = {urn:nbn:de:0030-drops-43737},
doi = {10.4230/LIPIcs.FSTTCS.2013.201},
annote = {Keywords: Polynomials, Approximation, Compression, Circuit lower bounds}
}
Document
Implementing Realistic Asynchronous Automata
Abstract
Zielonka's theorem, established 25 years ago, states that any regular
language closed under commutation is the language of an asynchronous
automaton (a tuple of automata, one per process, exchanging information when performing common actions). Since then, constructing asynchronous automata has been simplified and improved ([Cori/Métivier/Zielonka,1993],[Klarlund/Mukund/Sohoni,1994], [Diekert/Rozenberg,1995], [Genest/Muscholl,2006], [Genest/Gimbert/Muscholl/Walukiewicz,2010], [Baudru/Morin, 2006], [Baudru,2009], [Pighizzini,1993], [Stefanescu/Esparza/Muscholl,2003]).
We first survey these constructions and conclude that the synthesized
systems are not realistic in the following sense: existing constructions are either plagued by deadends, non deterministic guesses, or the acceptance condition or choice of actions are not distributed. We tackle this problem by giving (effectively testable) necessary and sufficient conditions which ensure that deadends can be avoided, acceptance condition and choices of action can be distributed, and determinism can be maintained. Finally, we implement our constructions, giving promising results when compared with the few other existing prototypes synthesizing asynchronous automata.
Cite as
S. Akshay, Ionut Dinca, Blaise Genest, and Alin Stefanescu. Implementing Realistic Asynchronous Automata. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 213-224, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{akshay_et_al:LIPIcs.FSTTCS.2013.213,
author = {Akshay, S. and Dinca, Ionut and Genest, Blaise and Stefanescu, Alin},
title = {{Implementing Realistic Asynchronous Automata}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {213--224},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.213},
URN = {urn:nbn:de:0030-drops-43742},
doi = {10.4230/LIPIcs.FSTTCS.2013.213},
annote = {Keywords: Asynchronous automata, Zielonka construction, Implementability}
}
Document
Computation of Summaries Using Net Unfoldings
Abstract
We study the following summarization problem: given a parallel
composition A=A_1||...||A_n of labelled transition systems communicating with the environment through a distinguished component A_i, efficiently compute a summary S_i such that E||A and E||S_i are trace-equivalent for every environment E. While Si can be computed using elementary automata theory, the resulting algorithm suffers from the state-explosion problem. We present a new, simple but subtle algorithm based on net unfoldings, a partial-order semantics, give some experimental results using an implementation on top of MOLE, and show that our algorithm can handle divergences and compute weighted summaries with minor modifications.
Cite as
Javier Esparza, Loig Jezequel, and Stefan Schwoon. Computation of Summaries Using Net Unfoldings. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 225-236, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{esparza_et_al:LIPIcs.FSTTCS.2013.225,
author = {Esparza, Javier and Jezequel, Loig and Schwoon, Stefan},
title = {{Computation of Summaries Using Net Unfoldings}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {225--236},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.225},
URN = {urn:nbn:de:0030-drops-43759},
doi = {10.4230/LIPIcs.FSTTCS.2013.225},
annote = {Keywords: Net unfoldings, Concurrent systems, Petri nets}
}
Document
Faster Deterministic Algorithms for r-Dimensional Matching Using Representative Sets
Abstract
Given a universe U := U_1 + .... + U_r and a r-uniform family F
which is a subset of U_1 x .... x U_r, the r-dimensional matching
problem asks if F admits a collection of k mutually disjoint sets. The
special case when r=3 is the classic 3-Dimensional Matching problem.
Recently, several improvements have been suggested for these (and closely related) problems in the setting of randomized parameterized algorithms. Also, many approaches have evolved for deterministic parameterized algorithms. For instance, for the 3-Dimensional Matching problem, a combination of color coding and iterative expansion yields a running time of O^*(2.80^{(3k)}), and for the r-dimensional matching problem, a recently developed derandomization for known algebraic techniques leads to a running time of O^*(5.44^{(r-1)k}).
In this work, we employ techniques based on dynamic programming and
representative families, leading to a deterministic algorithm with running time O^*(2.85^{(r-1)k}) for the r-Dimensional Matching problem. Further, we incorporate the principles of iterative expansion used in the literature [TALG 2012] to obtain a better algorithm for 3D-matching, with a running time of O^*(2.003^{(3k)}). Apart from the significantly improved running times, we believe that these algorithms demonstrate an interesting application of representative families in conjunction with more traditional techniques.
Cite as
Prachi Goyal, Neeldhara Misra, and Fahad Panolan. Faster Deterministic Algorithms for r-Dimensional Matching Using Representative Sets. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 237-248, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{goyal_et_al:LIPIcs.FSTTCS.2013.237,
author = {Goyal, Prachi and Misra, Neeldhara and Panolan, Fahad},
title = {{Faster Deterministic Algorithms for r-Dimensional Matching Using Representative Sets}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {237--248},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.237},
URN = {urn:nbn:de:0030-drops-43761},
doi = {10.4230/LIPIcs.FSTTCS.2013.237},
annote = {Keywords: 3-Dimensional Matching, Fixed-Parameter Algorithms, Iterative Expansion}
}
Document
Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
Abstract
In this paper, we study a class of set cover problems that satisfy a special property which we call the small neighborhood cover property.
This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified distributed and parallel algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. These algorithms run in polylogarithmic communication rounds in the distributed setting and are in NC, in the parallel setting.
Cite as
Archita Agarwal, Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sambuddha Roy, and Yogish Sabharwal. Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 249-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2013.249,
author = {Agarwal, Archita and Chakaravarthy, Venkatesan T. and Choudhury, Anamitra Roy and Roy, Sambuddha and Sabharwal, Yogish},
title = {{Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {249--261},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.249},
URN = {urn:nbn:de:0030-drops-43775},
doi = {10.4230/LIPIcs.FSTTCS.2013.249},
annote = {Keywords: approximation algorithms, set cover problem, tree cover}
}
Document
Replica Placement via Capacitated Vertex Cover
Abstract
In this paper, we study the replica placement problem on trees and present a constant factor approximation algorithm (with an additional additive constant factor). This improves the best known previous algorithm having an approximation ratio dependent on the maximum degree of the tree. Our techniques also extend to the partial cover version. Our algorithms are based on the LP rounding technique. The core component of our algorithm exploits a connection between the natural LP solutions of the replica placement problem and the capacitated vertex cover problem.
Cite as
Sonika Arora, Venkatesan T. Chakaravarthy, Neelima Gupta, Koyel Mukherjee, and Yogish Sabharwal. Replica Placement via Capacitated Vertex Cover. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 263-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{arora_et_al:LIPIcs.FSTTCS.2013.263,
author = {Arora, Sonika and Chakaravarthy, Venkatesan T. and Gupta, Neelima and Mukherjee, Koyel and Sabharwal, Yogish},
title = {{Replica Placement via Capacitated Vertex Cover}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {263--274},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.263},
URN = {urn:nbn:de:0030-drops-43784},
doi = {10.4230/LIPIcs.FSTTCS.2013.263},
annote = {Keywords: Approximation Algorithms, LP Rounding}
}
Document
Knapsack Cover Subject to a Matroid Constraint
Abstract
We consider the Knapsack Covering problem subject to a matroid constraint. In this problem, we are given an universe U of n items where item i has attributes: a cost c(i) and a size s(i). We also have a demand D. We are also given a matroid M = (U, I) on the set U. A feasible solution S to the problem is one such that (i) the cumulative size of the items chosen is at least D, and (ii) the set S is independent in the matroid M (i.e. S is in I). The objective is to minimize the total cost of the items selected, sum_{i in S}c(i).
Our main result proves a 2-factor approximation for this problem.
The problem described above falls in the realm of mixed packing covering problems. We also consider packing extensions of certain other covering problems and prove that in such cases it is not possible to derive any constant factor pproximations.
Cite as
Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sivaramakrishnan R. Natarajan, and Sambuddha Roy. Knapsack Cover Subject to a Matroid Constraint. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2013.275,
author = {Chakaravarthy, Venkatesan T. and Choudhury, Anamitra Roy and Natarajan, Sivaramakrishnan R. and Roy, Sambuddha},
title = {{Knapsack Cover Subject to a Matroid Constraint}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {275--286},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.275},
URN = {urn:nbn:de:0030-drops-43795},
doi = {10.4230/LIPIcs.FSTTCS.2013.275},
annote = {Keywords: Approximation Algorithms, LP rounding, Matroid Constraints, Knapsack problems}
}
Document
Jumping Automata for Uniform Strategies
Abstract
The concept of uniform strategies has recently been proposed as a relevant notion in game theory for computer science. It relies on properties involving sets of plays in two-player turn-based arenas equipped with a binary relation between plays. Among the two notions of fully-uniform and strictly-uniform strategies, we focus on the latter, less explored. We present a language that extends CTL^* with a quantifier over all related plays, which enables to express a rich class of uniformity constraints on strategies. We show that the existence of a uniform strategy is equivalent to the language non-emptiness of a jumping tree automaton. While the existence of a uniform strategy is undecidable for rational binary relations, restricting to ecognizable relations yields a 2EXPTIME-complete complexity, and still captures a class of two-player imperfect-information games with epistemic temporal objectives. This result relies on a translation from jumping tree automata with recognizable relations to two-way tree automata.
Cite as
Bastien Maubert and Sophie Pinchinat. Jumping Automata for Uniform Strategies. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 287-298, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{maubert_et_al:LIPIcs.FSTTCS.2013.287,
author = {Maubert, Bastien and Pinchinat, Sophie},
title = {{Jumping Automata for Uniform Strategies}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {287--298},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.287},
URN = {urn:nbn:de:0030-drops-43801},
doi = {10.4230/LIPIcs.FSTTCS.2013.287},
annote = {Keywords: Games, Imperfect information, Uniform strategies, Jumping automata}
}
Document
Emptiness Of Alternating Tree Automata Using Games With Imperfect Information
Abstract
We consider the emptiness problem for alternating tree automata,
with two acceptance semantics: classical (all branches are accepted)
and qualitative (almost all branches are accepted). For the classical semantics, the usual technique to tackle this problem relies on a Simulation Theorem which constructs an equivalent non-deterministic automaton from the original alternating one, and then checks emptiness by a reduction to a two-player perfect information game.
However, for the qualitative semantics, no simulation of alternation by means of non-determinism is known.
We give an alternative technique to decide the emptiness problem of alternating tree automata, that does not rely on a Simulation Theorem.
Indeed, we directly reduce the emptiness problem to solving an imperfect information two-player parity game. Our new approach can successfully be applied to both semantics, and yields decidability results with optimal complexity; for the qualitative semantics, the key ingredient in the proof is a positionality result for stochastic games played over infinite graphs.
Cite as
Nathanaël Fijalkow, Sophie Pinchinat, and Olivier Serre. Emptiness Of Alternating Tree Automata Using Games With Imperfect Information. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 299-311, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{fijalkow_et_al:LIPIcs.FSTTCS.2013.299,
author = {Fijalkow, Nathana\"{e}l and Pinchinat, Sophie and Serre, Olivier},
title = {{Emptiness Of Alternating Tree Automata Using Games With Imperfect Information}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {299--311},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.299},
URN = {urn:nbn:de:0030-drops-43812},
doi = {10.4230/LIPIcs.FSTTCS.2013.299},
annote = {Keywords: Alternating Automata, Emptiness checking, Two-player games, Imperfect Information Games}
}
Document
Saturation of Concurrent Collapsible Pushdown Systems
Abstract
Multi-stack pushdown systems are a well-studied model of concurrent computation using threads with first-order procedure calls. While, in general, reachability is undecidable, there are numerous restrictions on stack behaviour that lead to decidability. To model higher-order procedures calls, a generalisation of pushdown stacks called collapsible pushdown stacks are required. Reachability
problems for multi-stack collapsible pushdown systems have been little studied. Here, we study ordered, phase-bounded and scope-bounded multi-stack collapsible pushdown systems using saturation techniques, showing decidability of control state reachability and giving a regular representation of all configurations that can reach a given control state.
Cite as
Matthew Hague. Saturation of Concurrent Collapsible Pushdown Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 313-325, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{hague:LIPIcs.FSTTCS.2013.313,
author = {Hague, Matthew},
title = {{Saturation of Concurrent Collapsible Pushdown Systems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {313--325},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.313},
URN = {urn:nbn:de:0030-drops-43829},
doi = {10.4230/LIPIcs.FSTTCS.2013.313},
annote = {Keywords: Concurrency, Automata, Higher-Order, Verification, Model-Checking}
}
Document
Decidability Results on the Existence of Lookahead Delegators for NFA
Abstract
In this paper, we study lookahead delegators for nondeterministic finite automata (NFA), which are functions that deterministically choose transitions by additionally using a bounded lookahead on the input word. Of course, the delegator has to lead to an accepting state for each word that is accepted by the NFA. In the special case where no lookahead is allowed, a delegator coincides with a deterministic transition function that preserves the language.
Typical decision problems are to decide whether a delegator with a given fixed lookahead exists, or whether a delegator with some bounded lookahead exists for a given NFA. In a paper of Ravikumar and Santean from 2007, the complexity and decidability of these questions have been tackled, mainly for the case of unambiguous NFA. In this paper, we revisit the subject and provide results for the case of general NFA. First, we correct a complexity result from the above paper by showing that the existence of delegators with fixed lookahead can be decided in time polynomial in the number of states. We use two player games on graphs as a tool to obtain the result.
As second contribution, we show that the problem becomes PSPACE-complete if the bound on the lookahead is a part of the input.
The third result provides a bound on the maximal required amount of lookahead. We use this to show that the (previously open) problem of deciding the existence of a bounded lookahead delegator is also PSPACE-complete.
Cite as
Christof Löding and Stefan Repke. Decidability Results on the Existence of Lookahead Delegators for NFA. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 327-338, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{loding_et_al:LIPIcs.FSTTCS.2013.327,
author = {L\"{o}ding, Christof and Repke, Stefan},
title = {{Decidability Results on the Existence of Lookahead Delegators for NFA}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {327--338},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.327},
URN = {urn:nbn:de:0030-drops-43838},
doi = {10.4230/LIPIcs.FSTTCS.2013.327},
annote = {Keywords: Automata, Lookahead Delegators, Safety Games}
}
Document
Fair Matchings and Related Problems
Abstract
Let G = (A union B, E) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r be the worst rank used. A matching M is fair in G if it has maximum cardinality, subject to this, M matches the minimum number of vertices to rank r neighbors, subject to that, M matches the minimum number of vertices to rank (r-1) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G. We also show a scaling based algorithm for the fair b-matching problem.
Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation---this can be of independent interest.
Cite as
Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail. Fair Matchings and Related Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 339-350, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{huang_et_al:LIPIcs.FSTTCS.2013.339,
author = {Huang, Chien-Chung and Kavitha, Telikepalli and Mehlhorn, Kurt and Michail, Dimitrios},
title = {{Fair Matchings and Related Problems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {339--350},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.339},
URN = {urn:nbn:de:0030-drops-43841},
doi = {10.4230/LIPIcs.FSTTCS.2013.339},
annote = {Keywords: Matching with Preferences, Fairness and Rank-Maximality, Bipartite Vertex Cover, Linear Programming Duality, Complementary Slackness}
}
Document
Ranking with Diverse Intents and Correlated Contents
Abstract
We consider the following document ranking problem: We have a collection of documents, each containing some topics (e.g. sports, politics, economics). We also have a set of users with diverse interests. Assume that user u is interested in a subset I_u of topics. Each user u is also associated with a positive integer K_u,
which indicates that u can be satisfied by any K_u topics in I_u. Each document s contains information for a subset C_s of topics. The objective is to pick one document at a time such that the average satisfying time is minimized, where a user's satisfying time is the first time that at least K_u topics in I_u are covered in the documents selected so far.
Our main result is an O(rho)-approximation algorithm for the problem, where rho is the algorithmic integrality gap of the linear programming relaxation of the set cover instance defined by the documents and topics. This result generalizes the constant approximations for generalized min-sum set cover and ranking with unrelated intents and the logarithmic approximation for the problem of ranking with submodular valuations (when the submodular function is the coverage function), and can be seen as an interpolation between these results. We further extend our model to the case when each user may be interested in more than one sets of topics and when the user's valuation function is XOS, and obtain similar results for these models.
Cite as
Jian Li and Zeyu Zhang. Ranking with Diverse Intents and Correlated Contents. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 351-362, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{li_et_al:LIPIcs.FSTTCS.2013.351,
author = {Li, Jian and Zhang, Zeyu},
title = {{Ranking with Diverse Intents and Correlated Contents}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {351--362},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.351},
URN = {urn:nbn:de:0030-drops-43856},
doi = {10.4230/LIPIcs.FSTTCS.2013.351},
annote = {Keywords: Approximation Algorithm, Diversification, min-sum Set Cover}
}
Document
Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages
Abstract
A separator for two languages is a third language containing the first one and disjoint from the second one. We investigate the following decision problem: given two regular input languages, decide whether there exists a locally testable (resp. a locally threshold testable) separator. In both cases, we design a decision procedure based on the occurrence of special patterns in automata accepting the input languages. We prove that the problem is computationally harder than deciding membership. The correctness proof of the algorithm yields a stronger result, namely a description of a possible separator. Finally, we discuss the same problem for context-free input languages.
Cite as
Thomas Place, Lorijn van Rooijen, and Marc Zeitoun. Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 363-375, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{place_et_al:LIPIcs.FSTTCS.2013.363,
author = {Place, Thomas and van Rooijen, Lorijn and Zeitoun, Marc},
title = {{Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {363--375},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.363},
URN = {urn:nbn:de:0030-drops-43867},
doi = {10.4230/LIPIcs.FSTTCS.2013.363},
annote = {Keywords: Automata, Logics, Monoids, Locally testable, Separation, Context-free.}
}
Document
On the Structure and Complexity of Rational Sets of Regular Languages
Abstract
In the recently designed and implemented test specification language FQL, relevant test goals are specified as regular expressions over program locations. To transition from single test goals to test suites, FQL describes suites as regular expressions over finite alphabets where each symbol corresponds to a regular expression over program locations. Hence, each word in a test suite expression yields a test goal specification. Such test suite specifications are in fact rational sets of regular languages (RSRLs). We show closure properties of general and finite RSRLs under common set theoretic operations. We also prove complexity results for checking equivalence and inclusion of star-free RSRLs and for checking whether a regular language is a member of a general or star-free RSRL. As the star-free (and thus finite) case underlies FQL specifications, the closure and complexity results provide a systematic foundation for FQL test specifications.
Cite as
Andreas Holzer, Christian Schallhart, Michael Tautschnig, and Helmut Veith. On the Structure and Complexity of Rational Sets of Regular Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 377-388, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{holzer_et_al:LIPIcs.FSTTCS.2013.377,
author = {Holzer, Andreas and Schallhart, Christian and Tautschnig, Michael and Veith, Helmut},
title = {{On the Structure and Complexity of Rational Sets of Regular Languages}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {377--388},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.377},
URN = {urn:nbn:de:0030-drops-43871},
doi = {10.4230/LIPIcs.FSTTCS.2013.377},
annote = {Keywords: Rational Sets, Regular Languages, Test Specification in FQL, Closure Properties, Decision Problems}
}
Document
Geometric Avatar Problems
Abstract
We introduce the concept of Avatar problems that deal with situations where each entity has multiple copies or "avatars" and the solutions are constrained to use exactly one of the avatars. The resulting set of problems show a surprising range of hardness characteristics and elicit a variety of algorithmic solutions. Many Multiple geometric avatar problems are considered. In particular, we show how to extend the concept of epsilon-kernels to find approximation algorithms for geometric avatar problems. Results for metric space graph avatar problems are also presented.
Cite as
Mario E. Consuegra and Giri Narasimhan. Geometric Avatar Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 389-400, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{consuegra_et_al:LIPIcs.FSTTCS.2013.389,
author = {Consuegra, Mario E. and Narasimhan, Giri},
title = {{Geometric Avatar Problems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {389--400},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.389},
URN = {urn:nbn:de:0030-drops-43889},
doi = {10.4230/LIPIcs.FSTTCS.2013.389},
annote = {Keywords: Avatar problems, choice}
}
Document
Clustering With Center Constraints
Abstract
In the classical maximum independent set problem, we are given a graph G of "conflicts" and are asked to find a maximum conflict-free subset. If we think of the remaining nodes as being "assigned" (at unit cost each) to one of these independent vertices and ask for an assignment of minimum cost, this yields the vertex cover problem.
In this paper, we consider a more general scenario where the assignment costs might be given by a distance metric d (which can be unrelated to G) on the underlying set of vertices.
This problem, in addition to being a natural generalization of vertex cover and an interesting variant of the k-median problem, also has connection to constrained clustering and database repair.
Understanding the relation between the conflict structure (the graph) and the distance structure (the metric) for this problem turns out to be the key to isolating its complexity. We show that when the two structures are unrelated, the problem inherits a trivial upper bound from vertex cover and provide an almost matching lower bound on hardness of approximation. We then prove a number of lower and upper bounds that depend on the relationship between the two structures, including polynomial time algorithms for special graphs.
Cite as
Parinya Chalermsook and Suresh Venkatasubramanian. Clustering With Center Constraints. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 401-412, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{chalermsook_et_al:LIPIcs.FSTTCS.2013.401,
author = {Chalermsook, Parinya and Venkatasubramanian, Suresh},
title = {{Clustering With Center Constraints}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {401--412},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.401},
URN = {urn:nbn:de:0030-drops-43898},
doi = {10.4230/LIPIcs.FSTTCS.2013.401},
annote = {Keywords: Clustering, vertex cover, approximation algorithms}
}
Document
On Infinite Words Determined by Stack Automata
Abstract
We characterize the infinite words determined by one-way stack automata. An infinite language L determines an infinite word alpha if every string in L is a prefix of alpha. If L is regular or context-free, it is known that alpha must be ultimately periodic. We extend this result to the class of languages recognized by one-way nondeterministic checking stack automata (1-NCSA). We then consider stronger classes of stack automata and show that they determine a class of infinite words which we call multilinear. We show that every multilinear word can be written in a form which is amenable to parsing. Finally, we consider the class of one-way multihead deterministic finite automata (1:multi-DFA). We show that every multilinear word can be determined by some 1:multi-DFA, but that there exist infinite words determined by 1:multi-DFA which are not multilinear.
Cite as
Tim Smith. On Infinite Words Determined by Stack Automata. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 413-424, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{smith:LIPIcs.FSTTCS.2013.413,
author = {Smith, Tim},
title = {{On Infinite Words Determined by Stack Automata}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {413--424},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.413},
URN = {urn:nbn:de:0030-drops-43692},
doi = {10.4230/LIPIcs.FSTTCS.2013.413},
annote = {Keywords: stack automaton, infinite word, pumping lemma, prefix language, multihead finite automaton}
}
Document
The Combinatorics of Non-determinism
Abstract
A deep connection exists between the interleaving semantics of concurrent processes and increasingly labelled combinatorial structures. In this paper we further explore this connection by studying the rich combinatorics of partially increasing structures underlying the operator of non-deterministic choice. Following the symbolic method of analytic combinatorics, we study the size of the computation trees induced by typical non-deterministic processes, providing a precise quantitative measure of the so-called "combinatorial explosion" phenomenon. Alternatively, we can see non-deterministic choice as encoding a family of tree-like partial orders. Measuring the (rather large) size of this family on average offers a key witness to the expressiveness of the choice operator. As a practical outcome of our quantitative study, we describe an efficient algorithm for generating computation paths uniformly at random.
Cite as
Olivier Bodini, Antoine Genitrini, and Frédéric Peschanski. The Combinatorics of Non-determinism. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 425-436, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{bodini_et_al:LIPIcs.FSTTCS.2013.425,
author = {Bodini, Olivier and Genitrini, Antoine and Peschanski, Fr\'{e}d\'{e}ric},
title = {{The Combinatorics of Non-determinism}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {425--436},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.425},
URN = {urn:nbn:de:0030-drops-43901},
doi = {10.4230/LIPIcs.FSTTCS.2013.425},
annote = {Keywords: Concurrency theory, Analytic combinatorics, Non-deterministic choice, Partially increasing trees, Uniform random generation}
}
Document
Renting a Cloud
Abstract
We consider the problem of efficiently scheduling jobs on data centers to minimize the cost of renting machines from "the cloud."
In the most basic cloud service model, cloud providers offer computers on demand from large pools installed in data centers.
Clients pay for use at an hourly rate. In order to minimize cost, each client needs to decide on the number of machines to be rented and the duration of renting each machine. This suggests the following
optimization problem, which we call Rent Minimization. There is a set J={j_1,j_2,...,j_n} of n jobs. Job j_i is released at time
r_i >= 0, has a deadline of d_i, and requires p_i>0 contiguous processing time, r_i,d_i,p_i in R. The jobs need to be scheduled on
identical parallel machines. Machines may be rented for any length of time; however, the cost of renting a machine for l>=0 time units is [l/D] (the smallest integer >= l/D) dollars, for some given large real D; in particular, one pays dollar 2 whether the machine is rented for D+1 or 2D time units. The goal is to schedule all the jobs in a way that minimizes the incurred rental cost.
In this paper, we develop offline and online algorithms for Rent Minimization problem. The algorithms achieve a constant factor approximation for the offline version and O(log(p_max/p_min)) for the online version, where p_max and p_min are the maximum and minimum processing time of the jobs respectively. We also show that no deterministic online algorithm can achieve an approximation factor better than log_{3}(p_max/p_min) within a constant factor. Both of these algorithms use the well-studied problem of Machine Minimization as a subroutine. Machine Minimization is a special case of Rent Minimization where D = max_{i}{d_i}. In the process of solving the Rent Minimization problem, in this paper, we also develop the first online algorithm for Machine Minimization.
Cite as
Barna Saha. Renting a Cloud. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 437-448, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{saha:LIPIcs.FSTTCS.2013.437,
author = {Saha, Barna},
title = {{Renting a Cloud}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {437--448},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.437},
URN = {urn:nbn:de:0030-drops-43918},
doi = {10.4230/LIPIcs.FSTTCS.2013.437},
annote = {Keywords: Scheduling Algorithm, Online Algorithm, Approximation Algorithm}
}
Document
Energy Efficient Scheduling and Routing via Randomized Rounding
Abstract
We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed-scalable processors in a fully heterogeneous setting.
For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
Cite as
Evripidis Bampis, Alexander Kononov, Dimitrios Letsios, Giorgio Lucarelli, and Maxim Sviridenko. Energy Efficient Scheduling and Routing via Randomized Rounding. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 449-460, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{bampis_et_al:LIPIcs.FSTTCS.2013.449,
author = {Bampis, Evripidis and Kononov, Alexander and Letsios, Dimitrios and Lucarelli, Giorgio and Sviridenko, Maxim},
title = {{Energy Efficient Scheduling and Routing via Randomized Rounding}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {449--460},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.449},
URN = {urn:nbn:de:0030-drops-43923},
doi = {10.4230/LIPIcs.FSTTCS.2013.449},
annote = {Keywords: Randomized rounding; scheduling; approximation; energy-aware; configuration linear program}
}
Document
PTAS for Ordered Instances of Resource Allocation Problems
Abstract
We consider the problem of fair allocation of indivisible goods where
we are given a set I of m indivisible resources (items) and a set P of n customers (players) competing for the resources. Each resource
j in I has a same value vj > 0 for a subset of customers interested in j and it has no value for other customers. The goal is to find a feasible allocation of the resources to the interested customers such that in the Max-Min scenario (also known as Santa Claus problem) the minimum utility (sum of the resources) received by each of the customers is as high as possible and in the Min-Max case (also known as R||C_max problem), the maximum utility is as low as possible.
In this paper we are interested in instances of the problem that admit a PTAS. These instances are not only of theoretical interest but also have practical applications. For the Max-Min allocation problem, we start with instances of the problem that can be viewed as a convex bipartite graph; there exists an ordering of the resources such that each customer is interested (has positive evaluation) in a set of consecutive resources and we demonstrate a PTAS. For the Min-Max allocation problem, we obtain a PTAS for instances in which there is an ordering of the customers (machines) and each resource (job) is adjacent to a consecutive set of customers (machines).
Next we show that our method for the Max-Min scenario, can be extended to a broader class of bipartite graphs where the resources can be viewed as a tree and each customer is interested in a sub-tree of a bounded number of leaves of this tree (e.g. a sub-path).
Cite as
Kamyar Khodamoradi, Ramesh Krishnamurti, Arash Rafiey, and Georgios Stamoulis. PTAS for Ordered Instances of Resource Allocation Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 461-473, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{khodamoradi_et_al:LIPIcs.FSTTCS.2013.461,
author = {Khodamoradi, Kamyar and Krishnamurti, Ramesh and Rafiey, Arash and Stamoulis, Georgios},
title = {{PTAS for Ordered Instances of Resource Allocation Problems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {461--473},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.461},
URN = {urn:nbn:de:0030-drops-43936},
doi = {10.4230/LIPIcs.FSTTCS.2013.461},
annote = {Keywords: Approximation Algorithms, Convex Bipartite Graphs, Resource Allocation}
}
Document
On the Pseudoperiodic Extension of u^l = v^m w^n
Abstract
We investigate the solution set of the pseudoperiodic extension of the classical Lyndon and Sch\"utzenberger word equations. Consider u_1 ... u_l = v_1 ... v_m w_1 ... w_n, where u_i is in {u, theta(u)} for all 1 <= i <= l, v_j is in {v, theta(v)} for all 1 <= j <= m, w_k is in {w, theta(w)} for all 1 <= k <= n and u, v and w are variables, and theta is an antimorphic involution. A solution is called pseudoperiodic, if u,v,w are in {t, theta(t)}^+ for a word t. [Czeizler et al./I&C/2011] established that for small values of l, m, and n non-periodic solutions exist, and that for large enough values all solutions are pseudoperiodic. However, they leave a gap between those bounds which we close for a number of cases. Namely, we show that for l = 3 and either m,n >= 12 or m,n >= 5 and either m and n are not both even or not all u_i's are equal, all solutions are pseudoperiodic.
Cite as
Florin Manea, Mike Müller, and Dirk Nowotka. On the Pseudoperiodic Extension of u^l = v^m w^n. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 475-486, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{manea_et_al:LIPIcs.FSTTCS.2013.475,
author = {Manea, Florin and M\"{u}ller, Mike and Nowotka, Dirk},
title = {{On the Pseudoperiodic Extension of u^l = v^m w^n}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {475--486},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.475},
URN = {urn:nbn:de:0030-drops-43948},
doi = {10.4230/LIPIcs.FSTTCS.2013.475},
annote = {Keywords: Word equations, Pseudoperiodicity, Lyndon-Sch\"{u}tzenberger equation}
}
Document
Solvency Markov Decision Processes with Interest
Abstract
Solvency games, introduced by Berger et al., provide an abstract framework for modelling decisions of a risk-averse investor, whose goal is to avoid ever going broke. We study a new variant of this model, where, in addition to stochastic environment and fixed increments and decrements to the investor's wealth, we introduce
interest, which is earned or paid on the current level of savings or debt, respectively.
We study problems related to the minimum initial wealth sufficient to avoid bankruptcy (i.e. steady decrease of the wealth) with probability at least p. We present an exponential time algorithm which approximates this minimum initial wealth, and show that a polynomial time approximation is not possible unless P=NP.
For the qualitative case, i.e. p=1, we show that the problem whether a given number is larger than or equal to the minimum initial wealth belongs to NP \cap coNP, and show that a polynomial time algorithm would yield a polynomial time algorithm for mean-payoff games, existence of which is a longstanding open problem. We also identify some classes of solvency MDPs for which this problem is in P. In all above cases the algorithms also give corresponding bankruptcy avoiding strategies.
Cite as
Tomás Brázdil, Taolue Chen, Vojtech Forejt, Petr Novotný, and Aistis Simaitis. Solvency Markov Decision Processes with Interest. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 487-499, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{brazdil_et_al:LIPIcs.FSTTCS.2013.487,
author = {Br\'{a}zdil, Tom\'{a}s and Chen, Taolue and Forejt, Vojtech and Novotn\'{y}, Petr and Simaitis, Aistis},
title = {{Solvency Markov Decision Processes with Interest}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {487--499},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.487},
URN = {urn:nbn:de:0030-drops-43959},
doi = {10.4230/LIPIcs.FSTTCS.2013.487},
annote = {Keywords: Markov decision processes, algorithms, complexity, market models.}
}
Document
Parameterized Verification of Many Identical Probabilistic Timed Processes
Abstract
Parameterized verification aims at validating a system's model irrespective of the value of a parameter. We introduce a model for networks of identical probabilistic timed processes, where the number of processes is a parameter. Each process is a probabilistic single-clock timed automaton and communicates with the others by broadcasting. The number of processes either is constant (static case), or evolves over time through random disappearances and creations (dynamic case). An example of relevant parameterized verification problem for these systems is whether, independently of the number of processes, a configuration where one process is in a target state is reached almost-surely under all scheduling policies. On the one hand, most parameterized verification problems turn out to be undecidable in the static case (even for untimed processes). On the other hand, we prove their decidability in the dynamic case.
Cite as
Nathalie Bertrand and Paulin Fournier. Parameterized Verification of Many Identical Probabilistic Timed Processes. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 501-513, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{bertrand_et_al:LIPIcs.FSTTCS.2013.501,
author = {Bertrand, Nathalie and Fournier, Paulin},
title = {{Parameterized Verification of Many Identical Probabilistic Timed Processes}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {501--513},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.501},
URN = {urn:nbn:de:0030-drops-43964},
doi = {10.4230/LIPIcs.FSTTCS.2013.501},
annote = {Keywords: model checking, Markov decision processes, parameterized verification}
}
Document
Simulation Over One-counter Nets is PSPACE-Complete
Abstract
One-counter nets (OCN) are Petri nets with exactly one unbounded place.
They are equivalent to a subclass of one-counter automata with just a weak test for zero. Unlike many other semantic equivalences, strong and weak simulation preorder are decidable for OCN, but the computational complexity was an open problem. We show that both strong and weak simulation preorder on OCN are Pspace-complete.
Cite as
Piotr Hofman, Slawomir Lasota, Richard Mayr, and Patrick Totzke. Simulation Over One-counter Nets is PSPACE-Complete. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 515-526, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{hofman_et_al:LIPIcs.FSTTCS.2013.515,
author = {Hofman, Piotr and Lasota, Slawomir and Mayr, Richard and Totzke, Patrick},
title = {{Simulation Over One-counter Nets is PSPACE-Complete}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {515--526},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.515},
URN = {urn:nbn:de:0030-drops-43970},
doi = {10.4230/LIPIcs.FSTTCS.2013.515},
annote = {Keywords: Simulation preorder; one-counter nets; complexity}
}
Document
Optimal Constructions for Active Diagnosis
Abstract
The task of diagnosis consists in detecting, without ambiguity, occurrence of faults in a partially observed system. Depending on the degree of observability, a discrete event system may be
diagnosable or not. Active diagnosis aims at controlling the system in order to make it diagnosable. Solutions have already been proposed for the active diagnosis problem, but their complexity remains to be improved. We solve here the active diagnosability decision problem
and the active diagnoser synthesis problem, proving that (1) our
procedures are optimal w.r.t. to computational complexity, and (2) the memory required for the active diagnoser produced by the synthesis is minimal. We then focus on the delay between the occurrence of a fault and its detection by the diagnoser. We construct a memory-optimal diagnoser whose delay is at most twice the minimal delay, whereas the memory required for a diagnoser with optimal delay may be highly greater.
Cite as
Stefan Haar, Serge Haddad, Tarek Melliti, and Stefan Schwoon. Optimal Constructions for Active Diagnosis. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 527-539, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
Copy BibTex To Clipboard
@InProceedings{haar_et_al:LIPIcs.FSTTCS.2013.527,
author = {Haar, Stefan and Haddad, Serge and Melliti, Tarek and Schwoon, Stefan},
title = {{Optimal Constructions for Active Diagnosis}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {527--539},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Seth, Anil and Vishnoi, Nisheeth K.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.527},
URN = {urn:nbn:de:0030-drops-43981},
doi = {10.4230/LIPIcs.FSTTCS.2013.527},
annote = {Keywords: Diagnosis, Control theory, Automata theory, Games.}
}