48 Search Results for "Seth, Anil"

Volume

LIPIcs, Volume 24

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

FSTTCS 2013, December 12-14, 2013, Guwahati, India

Editors: Anil Seth and Nisheeth K. Vishnoi

Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2013
LIPIcs, Volume 24, FSTTCS'13, Complete Volume

Authors: Anil Seth and Nisheeth K. Vishnoi

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Anil Seth and Nisheeth K. Vishnoi

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.1
Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk)

Authors: Venkatesan Guruswami

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.3
Computing With a Fixed Number of Pointers (Invited Talk)

Authors: Martin Hofmann and Ramyaa Ramyaa

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.19
On Approximation Resistance of Predicates (Invited Talk)

Authors: Subhash Khot

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.21
Characterisations of Nowhere Dense Graphs (Invited Talk)

Authors: Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.41
Intersection Types for Normalization and Verification (Invited Talk)

Authors: Kazushige Terui

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.43
Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound

Authors: Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.55
On the Parameterised Complexity of String Morphism Problems

Authors: Henning Fernau, Markus L. Schmid, and Yngve Villanger

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.67
Partially Polynomial Kernels for Set Cover and Test Cover

Authors: Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.79
Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs

Authors: Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.91
Böhm Trees as Higher-Order Recursive Schemes

Authors: Pierre Clairambault and Andrzej S. Murawski

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.103
Evaluation is MSOL-compatible

Authors: Sylvain Salvati and Igor Walukiewicz

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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
DOI: 10.4230/LIPIcs.FSTTCS.2013.115
Model Checking and Functional Program Transformations

Authors: Axel Haddad

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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-dev.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}
}
  • Refine by Author
  • 3 Chakaravarthy, Venkatesan T.
  • 2 Choudhury, Anamitra Roy
  • 2 Pinchinat, Sophie
  • 2 Roy, Sambuddha
  • 2 Sabharwal, Yogish
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 Approximation Algorithms
  • 3 Automata
  • 2 Approximation Algorithm
  • 2 Kernelization
  • 2 Markov decision processes
  • Show More...

  • Refine by Type
  • 47 document
  • 1 volume

  • Refine by Publication Year
  • 47 2013
  • 1 2014

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact