LIPIcs, Volume 148
IPEC 2019, September 11-13, 2019, Munich, Germany
Editors: Bart M. P. Jansen and Jan Arne Telle
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Sylvain Salvati and Sophie Tison. Containment of Regular Path Queries Under Path Constraints. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{salvati_et_al:LIPIcs.ICDT.2024.17, author = {Salvati, Sylvain and Tison, Sophie}, title = {{Containment of Regular Path Queries Under Path Constraints}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {17:1--17:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.17}, URN = {urn:nbn:de:0030-drops-197994}, doi = {10.4230/LIPIcs.ICDT.2024.17}, annote = {Keywords: Graph databases, rational path queries, query containment, TGDs, word constraints, rewrite systems, finite controllability, decision problems} }
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, and Jun Yang. Computing Data Distribution from Query Selectivities. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agarwal_et_al:LIPIcs.ICDT.2024.18, author = {Agarwal, Pankaj K. and Raychaudhury, Rahul and Sintos, Stavros and Yang, Jun}, title = {{Computing Data Distribution from Query Selectivities}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.18}, URN = {urn:nbn:de:0030-drops-198007}, doi = {10.4230/LIPIcs.ICDT.2024.18}, annote = {Keywords: selectivity queries, discrete distributions, Multiplicative Weights Update, eps-approximation, learnable functions, depth problem, arrangement} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Approximate Circular Pattern Matching Under Edit Distance. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 24:1-24:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{charalampopoulos_et_al:LIPIcs.STACS.2024.24, author = {Charalampopoulos, Panagiotis and Pissis, Solon P. and Radoszewski, Jakub and Rytter, Wojciech and Wale\'{n}, Tomasz and Zuba, Wiktor}, title = {{Approximate Circular Pattern Matching Under Edit Distance}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {24:1--24:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.24}, URN = {urn:nbn:de:0030-drops-197346}, doi = {10.4230/LIPIcs.STACS.2024.24}, annote = {Keywords: circular pattern matching, approximate pattern matching, edit distance} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels M. P. Neumann. Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 21:1-21:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{briet_et_al:LIPIcs.ITCS.2024.21, author = {Bri\"{e}t, Jop and Buhrman, Harry and Castro-Silva, Davi and Neumann, Niels M. P.}, title = {{Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {21:1--21:11}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.21}, URN = {urn:nbn:de:0030-drops-195490}, doi = {10.4230/LIPIcs.ITCS.2024.21}, annote = {Keywords: Coding theory, circuit complexity, quantum complexity theory, higher-order Fourier analysis, non-local games} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Justin Y. Chen, Piotr Indyk, and David P. Woodruff. Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ITCS.2024.32, author = {Chen, Justin Y. and Indyk, Piotr and Woodruff, David P.}, title = {{Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {32:1--32:22}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.32}, URN = {urn:nbn:de:0030-drops-195605}, doi = {10.4230/LIPIcs.ITCS.2024.32}, annote = {Keywords: Streaming and Sketching Algorithms, Sublinear Algorithms} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. Electrical Flows for Polylogarithmic Competitive Oblivious Routing. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 55:1-55:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goranci_et_al:LIPIcs.ITCS.2024.55, author = {Goranci, Gramoz and Henzinger, Monika and R\"{a}cke, Harald and Sachdeva, Sushant and Sricharan, A. R.}, title = {{Electrical Flows for Polylogarithmic Competitive Oblivious Routing}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {55:1--55:22}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.55}, URN = {urn:nbn:de:0030-drops-195830}, doi = {10.4230/LIPIcs.ITCS.2024.55}, annote = {Keywords: oblivious routing, electrical flows} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 93:1-93:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{song_et_al:LIPIcs.ITCS.2024.93, author = {Song, Zhao and Zhang, Lichen and Zhang, Ruizhe}, title = {{Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {93:1--93:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.93}, URN = {urn:nbn:de:0030-drops-196212}, doi = {10.4230/LIPIcs.ITCS.2024.93}, annote = {Keywords: Deep learning theory, Nonconvex optimization} }
Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Shalom M. Asbell and Eric Ruppert. A Wait-Free Deque With Polylogarithmic Step Complexity. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{asbell_et_al:LIPIcs.OPODIS.2023.17, author = {Asbell, Shalom M. and Ruppert, Eric}, title = {{A Wait-Free Deque With Polylogarithmic Step Complexity}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {17:1--17:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.17}, URN = {urn:nbn:de:0030-drops-195073}, doi = {10.4230/LIPIcs.OPODIS.2023.17}, annote = {Keywords: Lock-Free, Wait-Free, Double-Ended Queue, Deque, Stack, Space-Bounded, Polylogarithmic, Linearizable} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Emmanuel Arrighi, Fedor V. Fomin, Petr A. Golovach, and Petra Wolf. Kernelizing Temporal Exploration Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.1, author = {Arrighi, Emmanuel and Fomin, Fedor V. and Golovach, Petr A. and Wolf, Petra}, title = {{Kernelizing Temporal Exploration Problems}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {1:1--1:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.1}, URN = {urn:nbn:de:0030-drops-194201}, doi = {10.4230/LIPIcs.IPEC.2023.1}, annote = {Keywords: Temporal graph, temporal exploration, computational complexity, kernel} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf. Cluster Editing with Overlapping Communities. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.2, author = {Arrighi, Emmanuel and Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Sullivan, Blair D. and Wolf, Petra}, title = {{Cluster Editing with Overlapping Communities}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {2:1--2:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.2}, URN = {urn:nbn:de:0030-drops-194218}, doi = {10.4230/LIPIcs.IPEC.2023.2}, annote = {Keywords: graph modification, correlation clustering, vertex splitting, NP-hardness, parameterized algorithm} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Budgeted Matroid Maximization: a Parameterized Viewpoint. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{doronarad_et_al:LIPIcs.IPEC.2023.13, author = {Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas}, title = {{Budgeted Matroid Maximization: a Parameterized Viewpoint}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.13}, URN = {urn:nbn:de:0030-drops-194329}, doi = {10.4230/LIPIcs.IPEC.2023.13}, annote = {Keywords: budgeted matching, budgeted matroid intersection, knapsack problems, FPT-approximation scheme} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl. Computing Complexity Measures of Degenerate Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{drange_et_al:LIPIcs.IPEC.2023.14, author = {Drange, P\r{a}l Gr{\o}n\r{a}s and Greaves, Patrick and Muzi, Irene and Reidl, Felix}, title = {{Computing Complexity Measures of Degenerate Graphs}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {14:1--14:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.14}, URN = {urn:nbn:de:0030-drops-194333}, doi = {10.4230/LIPIcs.IPEC.2023.14}, annote = {Keywords: vc-dimension, datastructure, degeneracy, enumerating} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Bart M. P. Jansen and Bart van der Steenhoven. Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jansen_et_al:LIPIcs.IPEC.2023.27, author = {Jansen, Bart M. P. and van der Steenhoven, Bart}, title = {{Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.27}, URN = {urn:nbn:de:0030-drops-194466}, doi = {10.4230/LIPIcs.IPEC.2023.27}, annote = {Keywords: kernelization, counting problems, feedback vertex set, dominating set, protrusion decomposition} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Bart M. P. Jansen and Shivesh K. Roy. On the Parameterized Complexity of Multiway Near-Separator. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jansen_et_al:LIPIcs.IPEC.2023.28, author = {Jansen, Bart M. P. and Roy, Shivesh K.}, title = {{On the Parameterized Complexity of Multiway Near-Separator}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {28:1--28:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.28}, URN = {urn:nbn:de:0030-drops-194470}, doi = {10.4230/LIPIcs.IPEC.2023.28}, annote = {Keywords: fixed-parameter tractability, multiway cut, near-separator} }
Feedback for Dagstuhl Publishing