LIPIcs, Volume 2
FSTTCS 2008, December 9-11, 2008, Bangalore, India
Editors: Ramesh Hariharan, Madhavan Mukund, and V Vinay
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
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)
@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} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
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)
@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} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
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)
@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: } }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
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)
@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} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
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)
@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} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
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)
@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} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
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)
@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} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
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)
@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} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
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)
@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} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
Hubert Comon-Lundh. About models of security protocols. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 352-356, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{comonlundh:LIPIcs.FSTTCS.2008.1766, author = {Comon-Lundh, Hubert}, title = {{About models of security protocols}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {352--356}, 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.1766}, URN = {urn:nbn:de:0030-drops-17662}, doi = {10.4230/LIPIcs.FSTTCS.2008.1766}, annote = {Keywords: Protocols, security, concurrency, formal methods} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
Rayna Dimitrova and Bernd Finkbeiner. Abstraction Refinement for Games with Incomplete Information. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 175-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{dimitrova_et_al:LIPIcs.FSTTCS.2008.1751, author = {Dimitrova, Rayna and Finkbeiner, Bernd}, title = {{Abstraction Refinement for Games with Incomplete Information}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {175--186}, 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.1751}, URN = {urn:nbn:de:0030-drops-17510}, doi = {10.4230/LIPIcs.FSTTCS.2008.1751}, annote = {Keywords: Automatic abstraction refinement, synthesis} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
Krishnendu Chatterjee, Luca de Alfaro, Rupak Majumdar, and Vishwanath Raman. Algorithms for Game Metrics. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 107-118, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{chatterjee_et_al:LIPIcs.FSTTCS.2008.1745, author = {Chatterjee, Krishnendu and de Alfaro, Luca and Majumdar, Rupak and Raman, Vishwanath}, title = {{Algorithms for Game Metrics}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {107--118}, 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.1745}, URN = {urn:nbn:de:0030-drops-17455}, doi = {10.4230/LIPIcs.FSTTCS.2008.1745}, annote = {Keywords: Algorithms, Metrics, Kernel, Simulation, Bisimulation, Linear Programming, Theory of Reals} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
Daniel Golovin, Anupam Gupta, Amit Kumar, and Kanat Tangwongsan. All-Norms and All-L_p-Norms Approximation Algorithms. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 199-210, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{golovin_et_al:LIPIcs.FSTTCS.2008.1753, author = {Golovin, Daniel and Gupta, Anupam and Kumar, Amit and Tangwongsan, Kanat}, title = {{All-Norms and All-L\underlinep-Norms Approximation Algorithms}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {199--210}, 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.1753}, URN = {urn:nbn:de:0030-drops-17537}, doi = {10.4230/LIPIcs.FSTTCS.2008.1753}, annote = {Keywords: Approximation algorithms, set-cover problems, combinatorial optimization, sampling minkowski norms} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
Stefan Gulan and Henning Fernau. An Optimal Construction of Finite Automata from Regular Expressions. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 211-222, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{gulan_et_al:LIPIcs.FSTTCS.2008.1754, author = {Gulan, Stefan and Fernau, Henning}, title = {{An Optimal Construction of Finite Automata from Regular Expressions}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {211--222}, 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.1754}, URN = {urn:nbn:de:0030-drops-17544}, doi = {10.4230/LIPIcs.FSTTCS.2008.1754}, annote = {Keywords: Finite automata,regular expressions,descriptional complexity} }
Feedback for Dagstuhl Publishing