Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Euiwoong Lee and Pasin Manurangsi. Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 71:1-71:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lee_et_al:LIPIcs.ITCS.2024.71, author = {Lee, Euiwoong and Manurangsi, Pasin}, title = {{Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {71:1--71:17}, 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.71}, URN = {urn:nbn:de:0030-drops-195996}, doi = {10.4230/LIPIcs.ITCS.2024.71}, annote = {Keywords: Hardness of Approximation, Bounded Degree, Constraint Satisfaction Problems, Independent Set} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad, and Kheeran K. Naidu. Improved Weighted Matching in the Sliding Window Model. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 6:1-6:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{alexandru_et_al:LIPIcs.STACS.2023.6, author = {Alexandru, Cezar-Mihail and Dvo\v{r}\'{a}k, Pavel and Konrad, Christian and Naidu, Kheeran K.}, title = {{Improved Weighted Matching in the Sliding Window Model}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {6:1--6:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.6}, URN = {urn:nbn:de:0030-drops-176585}, doi = {10.4230/LIPIcs.STACS.2023.6}, annote = {Keywords: Sliding window algorithms, Streaming algorithms, Maximum-weight matching} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Pavel Dvořák, Tomáš Masařík, Jana Novotná, Monika Krawczyk, Paweł Rzążewski, and Aneta Żuk. List Locally Surjective Homomorphisms in Hereditary Graph Classes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 30:1-30:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2022.30, author = {Dvo\v{r}\'{a}k, Pavel and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Krawczyk, Monika and Rz\k{a}\.{z}ewski, Pawe{\l} and \.{Z}uk, Aneta}, title = {{List Locally Surjective Homomorphisms in Hereditary Graph Classes}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {30:1--30:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.30}, URN = {urn:nbn:de:0030-drops-173154}, doi = {10.4230/LIPIcs.ISAAC.2022.30}, annote = {Keywords: Homomorphism, Hereditary graphs, Subexponential-time algorithms} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Pavel Dvořák, Michal Koucký, Karel Král, and Veronika Slívová. Data Structures Lower Bounds and Popular Conjectures. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 39:1-39:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dvorak_et_al:LIPIcs.ESA.2021.39, author = {Dvo\v{r}\'{a}k, Pavel and Kouck\'{y}, Michal and Kr\'{a}l, Karel and Sl{\'\i}vov\'{a}, Veronika}, title = {{Data Structures Lower Bounds and Popular Conjectures}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.39}, URN = {urn:nbn:de:0030-drops-146207}, doi = {10.4230/LIPIcs.ESA.2021.39}, annote = {Keywords: Data structures, Circuits, Lower bounds, Network Coding Conjecture} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Pavel Dvořák and Michal Koucký. Barrington Plays Cards: The Complexity of Card-Based Protocols. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 26:1-26:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dvorak_et_al:LIPIcs.STACS.2021.26, author = {Dvo\v{r}\'{a}k, Pavel and Kouck\'{y}, Michal}, title = {{Barrington Plays Cards: The Complexity of Card-Based Protocols}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {26:1--26:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.26}, URN = {urn:nbn:de:0030-drops-136715}, doi = {10.4230/LIPIcs.STACS.2021.26}, annote = {Keywords: Efficient card-based protocol, Branching program, Turing machine} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Pavel Dvořák and Bruno Loff. Lower Bounds for Semi-adaptive Data Structures via Corruption. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 20:1-20:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{dvorak_et_al:LIPIcs.FSTTCS.2020.20, author = {Dvo\v{r}\'{a}k, Pavel and Loff, Bruno}, title = {{Lower Bounds for Semi-adaptive Data Structures via Corruption}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {20:1--20:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.20}, URN = {urn:nbn:de:0030-drops-132617}, doi = {10.4230/LIPIcs.FSTTCS.2020.20}, annote = {Keywords: semi-adaptive dynamic data structure, polynomial lower bound, corruption bound, information theory} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, and Anastasia Sofronova. Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{galesi_et_al:LIPIcs.MFCS.2019.49, author = {Galesi, Nicola and Itsykson, Dmitry and Riazanov, Artur and Sofronova, Anastasia}, title = {{Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {49:1--49:15}, 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.49}, URN = {urn:nbn:de:0030-drops-109932}, doi = {10.4230/LIPIcs.MFCS.2019.49}, annote = {Keywords: Tseitin formula, treewidth, AC0-Frege} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Pavel Dvorák, Dusan Knop, and Tomás Toufar. Target Set Selection in Dense Graph Classes. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 18:1-18:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2018.18, author = {Dvor\'{a}k, Pavel and Knop, Dusan and Toufar, Tom\'{a}s}, title = {{Target Set Selection in Dense Graph Classes}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {18:1--18:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.18}, URN = {urn:nbn:de:0030-drops-99666}, doi = {10.4230/LIPIcs.ISAAC.2018.18}, annote = {Keywords: parameterized complexity, target set selection, dense graphs} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Pavel Dvorák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masarík, Tomáš Toufar, and Pavel Veselý. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 26:1-26:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{dvorak_et_al:LIPIcs.STACS.2018.26, author = {Dvor\'{a}k, Pavel and Feldmann, Andreas Emil and Knop, Du\v{s}an and Masar{\'\i}k, Tom\'{a}\v{s} and Toufar, Tom\'{a}\v{s} and Vesel\'{y}, Pavel}, title = {{Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {26:1--26:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.26}, URN = {urn:nbn:de:0030-drops-85158}, doi = {10.4230/LIPIcs.STACS.2018.26}, annote = {Keywords: Steiner Tree, Steiner Forest, Approximation Algorithms, Parameterized Algorithms, Lossy Kernelization} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Lower Bounds for Elimination via Weak Regularity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 21:1-21:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{chattopadhyay_et_al:LIPIcs.STACS.2017.21, author = {Chattopadhyay, Arkadev and Dvor\'{a}k, Pavel and Kouck\'{y}, Michal and Loff, Bruno and Mukhopadhyay, Sagnik}, title = {{Lower Bounds for Elimination via Weak Regularity}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.21}, URN = {urn:nbn:de:0030-drops-70128}, doi = {10.4230/LIPIcs.STACS.2017.21}, annote = {Keywords: communication complexity, elimination, discrepancy, regularity, greater-than} }
Feedback for Dagstuhl Publishing