LIPIcs, Volume 4
FSTTCS 2009, December 15-17, 2009, Kanpur, India
Editors: Ravi Kannan and K. Narayan Kumar
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Papri Dey, Ravi Kannan, Nick Ryder, and Nikhil Srivastava. Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dey_et_al:LIPIcs.ITCS.2023.42, author = {Dey, Papri and Kannan, Ravi and Ryder, Nick and Srivastava, Nikhil}, title = {{Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {42:1--42:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.42}, URN = {urn:nbn:de:0030-drops-175450}, doi = {10.4230/LIPIcs.ITCS.2023.42}, annote = {Keywords: Symbolic algorithms, numerical algorithms, linear algebra} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chia_et_al:LIPIcs.ISAAC.2020.47, author = {Chia, Nai-Hui and Gily\'{e}n, Andr\'{a}s and Lin, Han-Hsuan and Lloyd, Seth and Tang, Ewin and Wang, Chunhao}, title = {{Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {47:1--47:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.47}, URN = {urn:nbn:de:0030-drops-133916}, doi = {10.4230/LIPIcs.ISAAC.2020.47}, annote = {Keywords: sublinear algorithms, quantum-inspired, regression, importance sampling, quantum machine learning} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Proceedings{kannan_et_al:LIPIcs.FSTTCS.2009, title = {{LIPIcs, Volume 4, FSTTCS'09, 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-13-2}, ISSN = {1868-8969}, year = {2013}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009}, URN = {urn:nbn:de:0030-drops-40987}, doi = {10.4230/LIPIcs.FSTTCS.2009}, annote = {Keywords: LIPIcs, Volume 4, FSTTCS'09, Complete Volume} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. i-vii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{kannan_et_al:LIPIcs.FSTTCS.2009.2341, author = {Kannan, Ravi and Narayan Kumar, K.}, title = {{Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {i--vii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2341}, URN = {urn:nbn:de:0030-drops-23415}, doi = {10.4230/LIPIcs.FSTTCS.2009.2341}, annote = {Keywords: Preface, proceedings, FSTTCS, referees, programme committee, organising committee} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Mostafa Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram, and Richard J. Lipton. Algorithms for Message Ferrying on Mobile ad hoc Networks. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 13-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{ammar_et_al:LIPIcs.FSTTCS.2009.2303, author = {Ammar, Mostafa and Chakrabarty, Deeparnab and Sarma, Atish Das and Kalyanasundaram, Subrahmanyam and Lipton, Richard J.}, title = {{Algorithms for Message Ferrying on Mobile ad hoc Networks}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {13--24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2303}, URN = {urn:nbn:de:0030-drops-23031}, doi = {10.4230/LIPIcs.FSTTCS.2009.2303}, annote = {Keywords: Algorithms, Network Algorithms, Routing, TSP, Buffer Optimization} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan. Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2009.2304, author = {Arvind, Vikraman and Joglekar, Pushkar S. and Srinivasan, Srikanth}, title = {{Arithmetic Circuits and the Hadamard Product of Polynomials}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {25--36}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2304}, URN = {urn:nbn:de:0030-drops-23046}, doi = {10.4230/LIPIcs.FSTTCS.2009.2304}, annote = {Keywords: Hadamard product, identity testing, lower bounds, algebraic branching programs} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé. Kernels for Feedback Arc Set In Tournaments. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 37-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bessy_et_al:LIPIcs.FSTTCS.2009.2305, author = {Bessy, St\'{e}phane and Fomin, Fedor V. and Gaspers, Serge and Paul, Christophe and Perez, Anthony and Saurabh, Saket and Thomass\'{e}, St\'{e}phan}, title = {{Kernels for Feedback Arc Set In Tournaments}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {37--47}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2305}, URN = {urn:nbn:de:0030-drops-23055}, doi = {10.4230/LIPIcs.FSTTCS.2009.2305}, annote = {Keywords: Parameterized complexity, kernels, tournaments} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Tomas Brazdil, Javier Esparza, and Stefan Kiefer. On the Memory Consumption of Probabilistic Pushdown Automata. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 49-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{brazdil_et_al:LIPIcs.FSTTCS.2009.2306, author = {Brazdil, Tomas and Esparza, Javier and Kiefer, Stefan}, title = {{On the Memory Consumption of Probabilistic Pushdown Automata}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {49--60}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2306}, URN = {urn:nbn:de:0030-drops-23067}, doi = {10.4230/LIPIcs.FSTTCS.2009.2306}, annote = {Keywords: Pushdown automata, probabilistic systems, verification} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Tomas Brazdil, Vojtech Forejt, Jan Krcal, Jan Kretinsky, and Antonin Kucera. Continuous-Time Stochastic Games with Time-Bounded Reachability. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 61-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{brazdil_et_al:LIPIcs.FSTTCS.2009.2307, author = {Brazdil, Tomas and Forejt, Vojtech and Krcal, Jan and Kretinsky, Jan and Kucera, Antonin}, title = {{Continuous-Time Stochastic Games with Time-Bounded Reachability}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {61--72}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2307}, URN = {urn:nbn:de:0030-drops-23077}, doi = {10.4230/LIPIcs.FSTTCS.2009.2307}, annote = {Keywords: Continuous time stochastic systems, time bounded reachability, stochastic games} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Mikolaj Bojanczyk and Szymon Torunczyk. Deterministic Automata and Extensions of Weak MSO. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bojanczyk_et_al:LIPIcs.FSTTCS.2009.2308, author = {Bojanczyk, Mikolaj and Torunczyk, Szymon}, title = {{Deterministic Automata and Extensions of Weak MSO}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {73--84}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2308}, URN = {urn:nbn:de:0030-drops-23081}, doi = {10.4230/LIPIcs.FSTTCS.2009.2308}, annote = {Keywords: Deterministic automata, Weak MSO, min-automata, max-automata, BS-automata} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Laura Bozzelli, Axel Legay, and Sophie Pinchinat. On Timed Alternating Simulation for Concurrent Timed Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 85-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bozzelli_et_al:LIPIcs.FSTTCS.2009.2309, author = {Bozzelli, Laura and Legay, Axel and Pinchinat, Sophie}, title = {{On Timed Alternating Simulation for Concurrent Timed Games}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {85--96}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2309}, URN = {urn:nbn:de:0030-drops-23092}, doi = {10.4230/LIPIcs.FSTTCS.2009.2309}, annote = {Keywords: Concurrent Timed Games, Timed Alternating Simulation, Timed Alternating Temporal Logics} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Laurent Braud. Covering of ordinals. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 97-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{braud:LIPIcs.FSTTCS.2009.2310, author = {Braud, Laurent}, title = {{Covering of ordinals}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {97--108}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2310}, URN = {urn:nbn:de:0030-drops-23108}, doi = {10.4230/LIPIcs.FSTTCS.2009.2310}, annote = {Keywords: Ordinal theory, pushdown hierarchy, fundamental sequence, monadic second-order logic, prefix-recognizable graphs} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam, and Dustin Wehr. Fractional Pebbling and Thrifty Branching Programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 109-120, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{braverman_et_al:LIPIcs.FSTTCS.2009.2311, author = {Braverman, Mark and Cook, Stephen and McKenzie, Pierre and Santhanam, Rahul and Wehr, Dustin}, title = {{Fractional Pebbling and Thrifty Branching Programs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {109--120}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2311}, URN = {urn:nbn:de:0030-drops-23111}, doi = {10.4230/LIPIcs.FSTTCS.2009.2311}, annote = {Keywords: Branching programs, space complexity, tree evaluation, pebbling} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Jérémie Cabessa, Jacques Duparc, Alessandro Facchini, and Filip Murlak. The Wadge Hierarchy of Max-Regular Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 121-132, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{cabessa_et_al:LIPIcs.FSTTCS.2009.2312, author = {Cabessa, J\'{e}r\'{e}mie and Duparc, Jacques and Facchini, Alessandro and Murlak, Filip}, title = {{The Wadge Hierarchy of Max-Regular Languages}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {121--132}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, 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.2009.2312}, URN = {urn:nbn:de:0030-drops-23122}, doi = {10.4230/LIPIcs.FSTTCS.2009.2312}, annote = {Keywords: Max-regular languages, Wadge hierarchy, Wagner hierarchy} }
Feedback for Dagstuhl Publishing