45 Search Results for "Vinay, V"

Volume

LIPIcs, Volume 2

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

FSTTCS 2008, December 9-11, 2008, Bangalore, India

Editors: Ramesh Hariharan, Madhavan Mukund, and V Vinay

Document
DOI: 10.4230/LIPIcs.AofA.2024.2
Enumeration and Succinct Encoding of AVL Trees

Authors: Jeremy Chizewer, Stephen Melczer, J. Ian Munro, and Ava Pun

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We use a novel decomposition to create succinct data structures - supporting a wide range of operations on static trees in constant time - for a variety of tree classes, extending results of Munro, Nicholson, Benkner, and Wild. Motivated by the class of AVL trees, we further derive asymptotics for the information-theoretic lower bound on the number of bits needed to store tree classes whose generating functions satisfy certain functional equations. In particular, we prove that AVL trees require approximately 0.938 bits per node to encode.
Cite as

Jeremy Chizewer, Stephen Melczer, J. Ian Munro, and Ava Pun. Enumeration and Succinct Encoding of AVL Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chizewer_et_al:LIPIcs.AofA.2024.2,
  author =	{Chizewer, Jeremy and Melczer, Stephen and Munro, J. Ian and Pun, Ava},
  title =	{{Enumeration and Succinct Encoding of AVL Trees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.2},
  URN =		{urn:nbn:de:0030-drops-204376},
  doi =		{10.4230/LIPIcs.AofA.2024.2},
  annote =	{Keywords: AVL trees, analytic combinatorics, succinct data structures, enumeration}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.6
Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces

Authors: Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We consider the well-studied Robust (k,z)-Clustering problem, which generalizes the classic k-Median, k-Means, and k-Center problems and arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness [Abbasi, Bhaskara, Venkatasubramanian, 2021 & Ghadiri, Samadi, Vempala, 2022]. Given a constant z ≥ 1, the input to Robust (k,z)-Clustering is a set P of n points in a metric space (M,δ), a weight function w: P → ℝ_{≥ 0} and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S_1,S_2,…,S_m ⊆ P. Our goal is to find a set X of k centers such that max_{i ∈ [m]} ∑_{p ∈ S_i} w(p) δ(p,X)^z is minimized. Complementing recent work on this problem, we give a comprehensive understanding of the parameterized approximability of the problem in geometric spaces where the parameter is the number k of centers. We prove the following results: [(i)] 1) For a universal constant η₀ > 0.0006, we devise a 3^z(1-η₀)-factor FPT approximation algorithm for Robust (k,z)-Clustering in discrete high-dimensional Euclidean spaces where the set of potential centers is finite. This shows that the lower bound of 3^z for general metrics [Goyal, Jaiswal, Inf. Proc. Letters, 2023] no longer holds when the metric has geometric structure. 2) We show that Robust (k,z)-Clustering in discrete Euclidean spaces is (√{3/2}- o(1))-hard to approximate for FPT algorithms, even if we consider the special case k-Center in logarithmic dimensions. This rules out a (1+ε)-approximation algorithm running in time f(k,ε)poly(m,n) (also called efficient parameterized approximation scheme or EPAS), giving a striking contrast with the recent EPAS for the continuous setting where centers can be placed anywhere in the space [Abbasi et al., FOCS'23]. 3) However, we obtain an EPAS for Robust (k,z)-Clustering in discrete Euclidean spaces when the dimension is sublogarithmic (for the discrete problem, earlier work [Abbasi et al., FOCS'23] provides an EPAS only in dimension o(log log n)). Our EPAS works also for metrics of sub-logarithmic doubling dimension.
Cite as

Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abbasi_et_al:LIPIcs.ICALP.2024.6,
  author =	{Abbasi, Fateme and Banerjee, Sandip and Byrka, Jaros{\l}aw and Chalermsook, Parinya and Gadekar, Ameet and Khodamoradi, Kamyar and Marx, D\'{a}niel and Sharma, Roohani and Spoerhase, Joachim},
  title =	{{Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.6},
  URN =		{urn:nbn:de:0030-drops-201494},
  doi =		{10.4230/LIPIcs.ICALP.2024.6},
  annote =	{Keywords: Clustering, approximation algorithms, parameterized complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.24
Exponential Lower Bounds via Exponential Sums

Authors: Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Valiant’s famous VP vs. VNP conjecture states that the symbolic permanent polynomial does not have polynomial-size algebraic circuits. However, the best upper bound on the size of the circuits computing the permanent is exponential. Informally, VNP is an exponential sum of VP-circuits. In this paper we study whether, in general, exponential sums (of algebraic circuits) require exponential-size algebraic circuits. We show that the famous Shub-Smale τ-conjecture indeed implies such an exponential lower bound for an exponential sum. Our main tools come from parameterized complexity. Along the way, we also prove an exponential fpt (fixed-parameter tractable) lower bound for the parameterized algebraic complexity class VW⁰_{nb}[𝖯], assuming the same conjecture. VW⁰_{nb}[𝖯] can be thought of as the weighted sums of (unbounded-degree) circuits, where only ± 1 constants are cost-free. To the best of our knowledge, this is the first time the Shub-Smale τ-conjecture has been applied to prove explicit exponential lower bounds. Furthermore, we prove that when this class is fpt, then a variant of the counting hierarchy, namely the linear counting hierarchy collapses. Moreover, if a certain type of parameterized exponential sums is fpt, then integers, as well as polynomials with coefficients being definable in the linear counting hierarchy have subpolynomial τ-complexity. Finally, we characterize a related class VW[𝖥], in terms of permanents, where we consider an exponential sum of algebraic formulas instead of circuits. We show that when we sum over cycle covers that have one long cycle and all other cycles have constant length, then the resulting family of polynomials is complete for VW[𝖥] on certain types of graphs.
Cite as

Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta, and Saswata Mukherjee. Exponential Lower Bounds via Exponential Sums. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhattacharjee_et_al:LIPIcs.ICALP.2024.24,
  author =	{Bhattacharjee, Somnath and Bl\"{a}ser, Markus and Dutta, Pranjal and Mukherjee, Saswata},
  title =	{{Exponential Lower Bounds via Exponential Sums}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.24},
  URN =		{urn:nbn:de:0030-drops-201677},
  doi =		{10.4230/LIPIcs.ICALP.2024.24},
  annote =	{Keywords: Algebraic complexity, parameterized complexity, exponential sums, counting hierarchy, tau conjecture}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.68
A Tight Subexponential-Time Algorithm for Two-Page Book Embedding

Authors: Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani, and Mateusz Rychlicki

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into "pages", which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are of special importance as they are both NP-hard to compute and have specific applications. We obtain a 2^𝒪(√n) algorithm for computing a book embedding of an n-vertex graph on two pages - a result which is asymptotically tight under the Exponential Time Hypothesis. As a key tool in our approach, we obtain a single-exponential fixed-parameter algorithm for the same problem when parameterized by the treewidth of the input graph. We conclude by establishing the fixed-parameter tractability of computing minimum-page book embeddings when parameterized by the feedback edge number, settling an open question arising from previous work on the problem.
Cite as

Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani, and Mateusz Rychlicki. A Tight Subexponential-Time Algorithm for Two-Page Book Embedding. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.ICALP.2024.68,
  author =	{Ganian, Robert and M\"{u}ller, Haiko and Ordyniak, Sebastian and Paesani, Giacomo and Rychlicki, Mateusz},
  title =	{{A Tight Subexponential-Time Algorithm for Two-Page Book Embedding}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{68:1--68:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.68},
  URN =		{urn:nbn:de:0030-drops-202114},
  doi =		{10.4230/LIPIcs.ICALP.2024.68},
  annote =	{Keywords: book embedding, page number, subexponential algorithms, subhamiltonicity, feedback edge number}
}
Document
DOI: 10.4230/DagMan.10.1.1
Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)

Authors: James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter

Published in: Dagstuhl Manifestos, Volume 10, Issue 1 (2024)

Abstract
Knowledge Representation and Reasoning is a central, longstanding, and active area of Artificial Intelligence. Over the years it has evolved significantly; more recently it has been challenged and complemented by research in areas such as machine learning and reasoning under uncertainty. In July 2022,sser a Dagstuhl Perspectives workshop was held on Knowledge Representation and Reasoning. The goal of the workshop was to describe the state of the art in the field, including its relation with other areas, its shortcomings and strengths, together with recommendations for future progress. We developed this manifesto based on the presentations, panels, working groups, and discussions that took place at the Dagstuhl Workshop. It is a declaration of our views on Knowledge Representation: its origins, goals, milestones, and current foci; its relation to other disciplines, especially to Artificial Intelligence; and on its challenges, along with key priorities for the next decade.
Cite as

James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter. Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282). In Dagstuhl Manifestos, Volume 10, Issue 1, pp. 1-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{delgrande_et_al:DagMan.10.1.1,
  author =	{Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank},
  title =	{{Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)}},
  pages =	{1--61},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2024},
  volume =	{10},
  number =	{1},
  editor =	{Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagMan.10.1.1},
  URN =		{urn:nbn:de:0030-drops-201403},
  doi =		{10.4230/DagMan.10.1.1},
  annote =	{Keywords: Knowledge representation and reasoning, Applications of logics, Declarative representations, Formal logic}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.27
Determinants vs. Algebraic Branching Programs

Authors: Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We show that for every homogeneous polynomial of degree d, if it has determinantal complexity at most s, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most O(d⁵s). Moreover, we show that for most homogeneous polynomials, the width of the resulting homogeneous ABP is just s-1 and the size is at most O(ds). Thus, for constant degree homogeneous polynomials, their determinantal complexity and ABP complexity are within a constant factor of each other and hence, a super-linear lower bound for ABPs for any constant degree polynomial implies a super-linear lower bound on determinantal complexity; this relates two open problems of great interest in algebraic complexity. As of now, super-linear lower bounds for ABPs are known only for polynomials of growing degree [Mrinal Kumar, 2019; Prerona Chatterjee et al., 2022], and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor [Mrinal Kumar and Ben Lee Volk, 2022]. While determinantal complexity and ABP complexity are classically known to be polynomially equivalent [Meena Mahajan and V. Vinay, 1997], the standard transformation from the former to the latter incurs a polynomial blow up in size in the process, and thus, it was unclear if a super-linear lower bound for ABPs implies a super-linear lower bound on determinantal complexity. In particular, a size preserving transformation from determinantal complexity to ABPs does not appear to have been known prior to this work, even for constant degree polynomials.
Cite as

Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk. Determinants vs. Algebraic Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ITCS.2024.27,
  author =	{Chatterjee, Abhranil and Kumar, Mrinal and Volk, Ben Lee},
  title =	{{Determinants vs. Algebraic Branching Programs}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.27},
  URN =		{urn:nbn:de:0030-drops-195550},
  doi =		{10.4230/LIPIcs.ITCS.2024.27},
  annote =	{Keywords: Determinant, Algebraic Branching Program, Lower Bounds, Singular Variety}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS'08, Complete Volume

Authors: Ramesh Hariharan, Madhavan Mukund, and V Vinay

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

Abstract
LIPIcs, Volume 2, FSTTCS'08, Complete Volume
Cite as

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{hariharan_et_al:LIPIcs.FSTTCS.2008,
  title =	{{LIPIcs, Volume 2, FSTTCS'08, Complete Volume}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008},
  URN =		{urn:nbn:de:0030-drops-40966},
  doi =		{10.4230/LIPIcs.FSTTCS.2008},
  annote =	{Keywords: LIPIcs, Volume 2, FSTTCS'08, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FSTTCS.2008.1772
2008 Abstracts Collection -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Authors: Ramesh Hariharan, Madhavan Mukund, and V Vinay

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

Abstract
This volume contains the proceedings of the 28th international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), organized under the auspices of the Indian Association for Research in Computing Science (IARCS).
Cite as

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. i-xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hariharan_et_al:LIPIcs.FSTTCS.2008.1772,
  author =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  title =	{{2008 Abstracts Collection -- IARCS Annual Conference on  Foundations of Software Technology and Theoretical Computer Science}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{i--xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1772},
  URN =		{urn:nbn:de:0030-drops-17720},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1772},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1771
2008 Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Authors: Ramesh Hariharan, Madhavan Mukund, and V Vinay

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

Abstract
This volume contains the proceedings of the 28th international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), organized under the auspices of the Indian Association for Research in Computing Science (IARCS). This year's conference attracted 117 submissions. Each submission was reviewed by at least three independent referees. The final selection of the papers making up the programme was done through an electronic discussion on EasyChair, spanning two weeks, without a physical meeting of the Programme Committee (PC). All PC members participated actively in the discussion. We have five invited speakers this year: Hubert Comon-Lundh, Uriel Feige, Erich Graedel, Simon Peyton Jones and Leslie Valiant. We thank them for having readily accepted our invitation to talk at the conference and for providing abstracts (and even full papers) for the proceedings. We thank all the reviewers and PC members, without whose dedicated effort the conference would not be possible. We thank the Organizing Committee for making the arrangements for the conference. This year, the conference is being held at the Indian Institute of Science, Bangalore, as part of its centenary year celebrations. It is a great honour and privilege for the conference to be recognized and associated with the institute on this occasion. Finally, this year we have taken a decisive step in democratizing the conference by moving away from commercial publishers. Instead, we will be hosting the proceedings online, electronically, via the Dagstuhl Research Online Publication Server (DROPS). A complete copy of the proceedings will also be hosted on the FSTTCS website (www.fsttcs.org). The copyrights to the papers will reside not with the publishers but with the respective authors. The copyright is now governed by the Creative Commons attribution NC-ND. We do hope this direction will be sustained in the future.
Cite as

Ramesh Hariharan, Madhavan Mukund, and V Vinay. 2008 Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, p. -1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hariharan_et_al:LIPIcs.FSTTCS.2008.1771,
  author =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  title =	{{2008 Preface -- IARCS Annual Conference on  Foundations of Software Technology and Theoretical Computer Science}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{-1---1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1771},
  URN =		{urn:nbn:de:0030-drops-17713},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1771},
  annote =	{Keywords: Preface}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1749
3-connected Planar Graph Isomorphism is in Log-space

Authors: Samir Datta, Nutan Limaye, and Prajakta Nimbhorkar

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

Abstract
We consider the isomorphism and canonization problem for $3$-connected planar graphs. The problem was known to be \Log-hard and in \ULcoUL\ \cite{TW07}. In this paper, we give a deterministic log-space algorithm for $3$-connected planar graph isomorphism and canonization. This gives an \Log-completeness result, thereby settling its complexity. \par The algorithm uses the notion of universal exploration sequences from \cite{koucky01} and \cite{Rei05}. To our knowledge, this is a completely new approach to graph canonization.
Cite as

Samir Datta, Nutan Limaye, and Prajakta Nimbhorkar. 3-connected Planar Graph Isomorphism is in Log-space. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 155-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2008.1749,
  author =	{Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta},
  title =	{{3-connected Planar Graph Isomorphism is in Log-space}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{155--162},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1749},
  URN =		{urn:nbn:de:0030-drops-17491},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1749},
  annote =	{Keywords: Planar graph isomorphism, three connected graphs, logspace, universal exploration sequence}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1760
A Cubic-Vertex Kernel for Flip Consensus Tree

Authors: Christian Komusiewicz and Johannes Uhlmann

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

Abstract
Given a bipartite graph G=(V_c,V_t,E) and a non-negative integer k, the NP-complete Minimum-Flip Consensus Tree problem asks whether G can be transformed, using up to k edge insertions and deletions, into a graph that does not contain an induced P_5 with its first vertex in V_t (a so-called M-graph or Sigma-graph). This problem plays an important role in computational phylogenetics, V_c standing for the characters and V_t standing for taxa. Chen et al. [IEEE/ACM TCBB 2006] showed that Minimum-Flip Consensus Tree is NP-complete and presented a parameterized algorithm with running time O(6^k\cdot |V_t|\cdot |V_c|). Recently, Boecker et al. [IWPEC'08] presented a refined search tree algorithm with running time O(4.83^k(|V_t|+|V_c|) + |V_t|\cdot |V_c|). We complement these results by polynomial-time executable data reduction rules yielding a problem kernel with O(k^3) vertices.
Cite as

Christian Komusiewicz and Johannes Uhlmann. A Cubic-Vertex Kernel for Flip Consensus Tree. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 280-291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{komusiewicz_et_al:LIPIcs.FSTTCS.2008.1760,
  author =	{Komusiewicz, Christian and Uhlmann, Johannes},
  title =	{{A Cubic-Vertex Kernel for Flip Consensus Tree}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{280--291},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1760},
  URN =		{urn:nbn:de:0030-drops-17600},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1760},
  annote =	{Keywords: Fixed-parameter algorithm, problem kernel, NP-hard problem, graph modification problem, computational phylogenetics}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1764
A Hierarchy of Semantics for Non-deterministic Term Rewriting Systems

Authors: Juan Rodriguez-Hortala

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

Abstract
Formalisms involving some degree of nondeterminism are frequent in computer science. In particular, various programming or specification languages are based on term rewriting systems where confluence is not required. In this paper we examine three concrete possible semantics for non-determinism that can be assigned to those programs. Two of them --call-time choice and run-time choice-- are quite well-known, while the third one --plural semantics-- is investigated for the first time in the context of term rewriting based programming languages. We investigate some basic intrinsic properties of the semantics and establish some relationships between them: we show that the three semantics form a hierarchy in the sense of set inclusion, and we prove that call-time choice and plural semantics enjoy a remarkable compositionality property that fails for run-time choice; finally, we show how to express plural semantics within run-time choice by means of a program transformation, for which we prove its adequacy.
Cite as

Juan Rodriguez-Hortala. A Hierarchy of Semantics for Non-deterministic Term Rewriting Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 328-339, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{rodriguezhortala:LIPIcs.FSTTCS.2008.1764,
  author =	{Rodriguez-Hortala, Juan},
  title =	{{A Hierarchy of Semantics for Non-deterministic Term Rewriting Systems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{328--339},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1764},
  URN =		{urn:nbn:de:0030-drops-17643},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1764},
  annote =	{Keywords: Functional-logic programming, term rewriting systems, constructor-based rewriting logic, non-determinism, call-time choice semantics, run-time choice}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1752
A new approach to the planted clique problem

Authors: Alan Frieze and Ravi Kannan

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

Abstract
We study the problem of finding a large planted clique in the random graph $G_{n,1/2}$. We reduce the problem to that of maximising a three dimensional tensor over the unit ball in $n$ dimensions. This latter problem has not been well studied and so we hope that this reduction will eventually lead to an improved solution to the planted clique problem.
Cite as

Alan Frieze and Ravi Kannan. A new approach to the planted clique problem. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 187-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{frieze_et_al:LIPIcs.FSTTCS.2008.1752,
  author =	{Frieze, Alan and Kannan, Ravi},
  title =	{{A new approach to the planted clique problem}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{187--198},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1752},
  URN =		{urn:nbn:de:0030-drops-17521},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1752},
  annote =	{Keywords: Planted Clique, Tensor, Random Graph}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1750
A new upper bound for 3-SAT

Authors: Josep Diaz, Lefteris Kirousis, Dieter Mitsche, and Xavier Perez-Gimenez

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

Abstract
We show that a randomly chosen $3$-CNF formula over $n$ variables with clauses-to-variables ratio at least $4.4898$ is asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was $4.506$. The first such bound, independently discovered by many groups of researchers since 1983, was $5.19$. Several decreasing values between $5.19$ and $4.506$ were published in the years between. The probabilistic techniques we use for the proof are, we believe, of independent interest.
Cite as

Josep Diaz, Lefteris Kirousis, Dieter Mitsche, and Xavier Perez-Gimenez. A new upper bound for 3-SAT. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 163-174, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{diaz_et_al:LIPIcs.FSTTCS.2008.1750,
  author =	{Diaz, Josep and Kirousis, Lefteris and Mitsche, Dieter and Perez-Gimenez, Xavier},
  title =	{{A new upper bound for 3-SAT}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{163--174},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1750},
  URN =		{urn:nbn:de:0030-drops-17507},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1750},
  annote =	{Keywords: Satisfiability, 3-SAT, random, threshold}
}
  • Refine by Author
  • 3 Hariharan, Ramesh
  • 3 Mukund, Madhavan
  • 3 Vinay, V
  • 2 Chekuri, Chandra
  • 2 Horn, Florian
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algebraic complexity theory
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Computing methodologies → Artificial intelligence
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Information systems → Information integration
  • Show More...

  • Refine by Keyword
  • 3 Games
  • 2 Approximation
  • 2 complexity
  • 2 parameterized complexity
  • 1 2-Connected Graphs
  • Show More...

  • Refine by Type
  • 44 document
  • 1 volume

  • Refine by Publication Year
  • 38 2008
  • 6 2024
  • 1 2013

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact