Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Pavol Ďuriš, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen, and Peter Rossmanith. Randomization in Non-Uniform Finite Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 30:1-30:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{duris_et_al:LIPIcs.MFCS.2020.30, author = {\v{D}uri\v{s}, Pavol and Kr\'{a}lovi\v{c}, Rastislav and Kr\'{a}lovi\v{c}, Richard and Pardubsk\'{a}, Dana and Pa\v{s}en, Martin and Rossmanith, Peter}, title = {{Randomization in Non-Uniform Finite Automata}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {30:1--30:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.30}, URN = {urn:nbn:de:0030-drops-126987}, doi = {10.4230/LIPIcs.MFCS.2020.30}, annote = {Keywords: finite automata, non-uniform computation, randomization} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, and David Wehner. Finding Optimal Solutions With Neighborly Help. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{burjons_et_al:LIPIcs.MFCS.2019.78, author = {Burjons, Elisabet and Frei, Fabian and Hemaspaandra, Edith and Komm, Dennis and Wehner, David}, title = {{Finding Optimal Solutions With Neighborly Help}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {78:1--78:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.78}, URN = {urn:nbn:de:0030-drops-110221}, doi = {10.4230/LIPIcs.MFCS.2019.78}, annote = {Keywords: Critical Graphs, Computational Complexity, Structural Self-Reducibility, Minimality Problems, Colorability, Vertex Cover, Satisfiability, Reoptimization, Advice} }
Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Stefan Dobrev, Rastislav Královic, and Dana Pardubská. Treasure Hunt with Barely Communicating Agents. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 14:1-14:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{dobrev_et_al:LIPIcs.OPODIS.2017.14, author = {Dobrev, Stefan and Kr\'{a}lovic, Rastislav and Pardubsk\'{a}, Dana}, title = {{Treasure Hunt with Barely Communicating Agents}}, booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)}, pages = {14:1--14:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-061-3}, ISSN = {1868-8969}, year = {2018}, volume = {95}, editor = {Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.14}, URN = {urn:nbn:de:0030-drops-86346}, doi = {10.4230/LIPIcs.OPODIS.2017.14}, annote = {Keywords: parallel exhaustive search, treasure hunt, fault-tolerant search, weak coordination, black holes} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Dennis Komm, Rastislav Královic, Richard Královic, and Christian Kudahl. Advice Complexity of the Online Induced Subgraph Problem. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 59:1-59:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{komm_et_al:LIPIcs.MFCS.2016.59, author = {Komm, Dennis and Kr\'{a}lovic, Rastislav and Kr\'{a}lovic, Richard and Kudahl, Christian}, title = {{Advice Complexity of the Online Induced Subgraph Problem}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {59:1--59:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.59}, URN = {urn:nbn:de:0030-drops-64713}, doi = {10.4230/LIPIcs.MFCS.2016.59}, annote = {Keywords: online algorithms, advice complexity, induced subgraph problem} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 294-306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{dell_et_al:LIPIcs.IPEC.2015.294, author = {Dell, Holger and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and M\"{o}mke, Tobias}, title = {{Complexity and Approximability of Parameterized MAX-CSPs}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {294--306}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.294}, URN = {urn:nbn:de:0030-drops-55910}, doi = {10.4230/LIPIcs.IPEC.2015.294}, annote = {Keywords: Approximation, Structural Parameters, Constraint Satisfaction} }
Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)
Martin Schuster and Thomas Schwentick. Games for Active XML Revisited. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 60-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{schuster_et_al:LIPIcs.ICDT.2015.60, author = {Schuster, Martin and Schwentick, Thomas}, title = {{Games for Active XML Revisited}}, booktitle = {18th International Conference on Database Theory (ICDT 2015)}, pages = {60--75}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-79-8}, ISSN = {1868-8969}, year = {2015}, volume = {31}, editor = {Arenas, Marcelo and Ugarte, Mart{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.60}, URN = {urn:nbn:de:0030-drops-49773}, doi = {10.4230/LIPIcs.ICDT.2015.60}, annote = {Keywords: Active XML, Computational Complexity, Nested Words, Rewriting Games, Semistructured Data} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. Advice Complexity for a Class of Online Problems. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 116-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{boyar_et_al:LIPIcs.STACS.2015.116, author = {Boyar, Joan and Favrholdt, Lene M. and Kudahl, Christian and Mikkelsen, Jesper W.}, title = {{Advice Complexity for a Class of Online Problems}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {116--129}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.116}, URN = {urn:nbn:de:0030-drops-49086}, doi = {10.4230/LIPIcs.STACS.2015.116}, annote = {Keywords: online algorithms, advice complexity, asymmetric string guessing, advice complexity class AOC, covering designs} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Dennis Komm, Rastislav Královic, Richard Královic, and Tobias Mömke. Randomized Online Algorithms with High Probability Guarantees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 470-481, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{komm_et_al:LIPIcs.STACS.2014.470, author = {Komm, Dennis and Kr\'{a}lovic, Rastislav and Kr\'{a}lovic, Richard and M\"{o}mke, Tobias}, title = {{Randomized Online Algorithms with High Probability Guarantees}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {470--481}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.470}, URN = {urn:nbn:de:0030-drops-44803}, doi = {10.4230/LIPIcs.STACS.2014.470}, annote = {Keywords: Online Algorithms, Randomization, High Probability} }
Feedback for Dagstuhl Publishing