Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Nicolas Bousquet, Alice Joffard, and Paul Ouvrard. Linear Transformations Between Dominating Sets in the TAR-Model. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bousquet_et_al:LIPIcs.ISAAC.2020.37, author = {Bousquet, Nicolas and Joffard, Alice and Ouvrard, Paul}, title = {{Linear Transformations Between Dominating Sets in the TAR-Model}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {37:1--37:14}, 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.37}, URN = {urn:nbn:de:0030-drops-133812}, doi = {10.4230/LIPIcs.ISAAC.2020.37}, annote = {Keywords: reconfiguration, dominating sets, addition removal, connectivity, diameter, minor, treewidth} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, and Dmitry Sokolov. Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 28:1-28:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{derezende_et_al:LIPIcs.CCC.2020.28, author = {de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Risse, Kilian and Sokolov, Dmitry}, title = {{Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {28:1--28:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.28}, URN = {urn:nbn:de:0030-drops-125804}, doi = {10.4230/LIPIcs.CCC.2020.28}, annote = {Keywords: proof complexity, resolution, weak pigeonhole principle, perfect matching, sparse graphs} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Bruno Loff and Sagnik Mukhopadhyay. Lifting Theorems for Equality. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{loff_et_al:LIPIcs.STACS.2019.50, author = {Loff, Bruno and Mukhopadhyay, Sagnik}, title = {{Lifting Theorems for Equality}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {50:1--50:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.50}, URN = {urn:nbn:de:0030-drops-102892}, doi = {10.4230/LIPIcs.STACS.2019.50}, annote = {Keywords: Communication complexity, Query complexity, Simulation theorem, Equality function} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Egor Klenin and Alexander Kozachinskiy. One-Sided Error Communication Complexity of Gap Hamming Distance. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{klenin_et_al:LIPIcs.MFCS.2018.7, author = {Klenin, Egor and Kozachinskiy, Alexander}, title = {{One-Sided Error Communication Complexity of Gap Hamming Distance}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.7}, URN = {urn:nbn:de:0030-drops-95893}, doi = {10.4230/LIPIcs.MFCS.2018.7}, annote = {Keywords: Communication Complexity, Gap Hamming Distance, one-sided error} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Alice Paul, Daniel Freund, Aaron Ferber, David B. Shmoys, and David P. Williamson. Prize-Collecting TSP with a Budget Constraint. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{paul_et_al:LIPIcs.ESA.2017.62, author = {Paul, Alice and Freund, Daniel and Ferber, Aaron and Shmoys, David B. and Williamson, David P.}, title = {{Prize-Collecting TSP with a Budget Constraint}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {62:1--62:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.62}, URN = {urn:nbn:de:0030-drops-78375}, doi = {10.4230/LIPIcs.ESA.2017.62}, annote = {Keywords: approximation algorithms, traveling salesman problem} }
Feedback for Dagstuhl Publishing