Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, and Yury Makarychev. Two-Sided Kirszbraun Theorem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{backurs_et_al:LIPIcs.SoCG.2021.13, author = {Backurs, Arturs and Mahabadi, Sepideh and Makarychev, Konstantin and Makarychev, Yury}, title = {{Two-Sided Kirszbraun Theorem}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.13}, URN = {urn:nbn:de:0030-drops-138129}, doi = {10.4230/LIPIcs.SoCG.2021.13}, annote = {Keywords: Kirszbraun theorem, Lipschitz map, Outer-extension, Two-sided extension} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Arturs Backurs and Sariel Har-Peled. Submodular Clustering in Low Dimensions. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{backurs_et_al:LIPIcs.SWAT.2020.8, author = {Backurs, Arturs and Har-Peled, Sariel}, title = {{Submodular Clustering in Low Dimensions}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.8}, URN = {urn:nbn:de:0030-drops-122551}, doi = {10.4230/LIPIcs.SWAT.2020.8}, annote = {Keywords: clustering, covering, PTAS} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Dhruv Rohatgi. Conditional Hardness of Earth Mover Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{rohatgi:LIPIcs.APPROX-RANDOM.2019.12, author = {Rohatgi, Dhruv}, title = {{Conditional Hardness of Earth Mover Distance}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.12}, URN = {urn:nbn:de:0030-drops-112270}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.12}, annote = {Keywords: Earth Mover Distance, Hardness of Approximation, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Kyriakos Axiotis and Christos Tzamos. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{axiotis_et_al:LIPIcs.ICALP.2019.19, author = {Axiotis, Kyriakos and Tzamos, Christos}, title = {{Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.19}, URN = {urn:nbn:de:0030-drops-105952}, doi = {10.4230/LIPIcs.ICALP.2019.19}, annote = {Keywords: Knapsack, Fine-Grained Complexity, Dynamic Programming} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, and Nicole Wein. Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2019.47, author = {Dalirrooyfard, Mina and Williams, Virginia Vassilevska and Vyas, Nikhil and Wein, Nicole}, title = {{Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {47:1--47:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.47}, URN = {urn:nbn:de:0030-drops-106238}, doi = {10.4230/LIPIcs.ICALP.2019.47}, annote = {Keywords: approximation algorithms, fine-grained complexity, diameter, radius, eccentricities} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Amir Abboud and Arturs Backurs. Towards Hardness of Approximation for Polynomial Time Problems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 11:1-11:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{abboud_et_al:LIPIcs.ITCS.2017.11, author = {Abboud, Amir and Backurs, Arturs}, title = {{Towards Hardness of Approximation for Polynomial Time Problems}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {11:1--11:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.11}, URN = {urn:nbn:de:0030-drops-81443}, doi = {10.4230/LIPIcs.ITCS.2017.11}, annote = {Keywords: LCS, Edit Distance, Hardness in P} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Arturs Backurs and Anastasios Sidiropoulos. Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{backurs_et_al:LIPIcs.APPROX-RANDOM.2016.1, author = {Backurs, Arturs and Sidiropoulos, Anastasios}, title = {{Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l\underlinep Spaces}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {1:1--1:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.1}, URN = {urn:nbn:de:0030-drops-66241}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.1}, annote = {Keywords: metric embeddings, Hausdorff metric, distortion, dimension} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight Hardness Results for Maximum Weight Rectangles. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{backurs_et_al:LIPIcs.ICALP.2016.81, author = {Backurs, Arturs and Dikkala, Nishanth and Tzamos, Christos}, title = {{Tight Hardness Results for Maximum Weight Rectangles}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {81:1--81:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.81}, URN = {urn:nbn:de:0030-drops-62040}, doi = {10.4230/LIPIcs.ICALP.2016.81}, annote = {Keywords: Maximum Rectangles, Hardness in P} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Andris Ambainis, Arturs Backurs, Juris Smotrovs, and Ronald de Wolf. Optimal quantum query bounds for almost all Boolean functions. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 446-453, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{ambainis_et_al:LIPIcs.STACS.2013.446, author = {Ambainis, Andris and Backurs, Arturs and Smotrovs, Juris and de Wolf, Ronald}, title = {{Optimal quantum query bounds for almost all Boolean functions}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {446--453}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.446}, URN = {urn:nbn:de:0030-drops-39557}, doi = {10.4230/LIPIcs.STACS.2013.446}, annote = {Keywords: Quantum computing, query complexity, lower bounds, polynomial method} }
Feedback for Dagstuhl Publishing