Document

**Published in:** LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

In this paper, we prove a two-sided variant of the Kirszbraun theorem. Consider an arbitrary subset X of Euclidean space and its superset Y. Let f be a 1-Lipschitz map from X to ℝ^m. The Kirszbraun theorem states that the map f can be extended to a 1-Lipschitz map ̃ f from Y to ℝ^m. While the extension ̃ f does not increase distances between points, there is no guarantee that it does not decrease distances significantly. In fact, ̃ f may even map distinct points to the same point (that is, it can infinitely decrease some distances). However, we prove that there exists a (1 + ε)-Lipschitz outer extension f̃:Y → ℝ^{m'} that does not decrease distances more than "necessary". Namely, ‖f̃(x) - f̃(y)‖ ≥ c √{ε} min(‖x-y‖, inf_{a,b ∈ X} (‖x - a‖ + ‖f(a) - f(b)‖ + ‖b-y‖)) for some absolutely constant c > 0. This bound is asymptotically optimal, since no L-Lipschitz extension g can have ‖g(x) - g(y)‖ > L min(‖x-y‖, inf_{a,b ∈ X} (‖x - a‖ + ‖f(a) - f(b)‖ + ‖b-y‖)) even for a single pair of points x and y.
In some applications, one is interested in the distances ‖f̃(x) - f̃(y)‖ between images of points x,y ∈ Y rather than in the map f̃ itself. The standard Kirszbraun theorem does not provide any method of computing these distances without computing the entire map ̃ f first. In contrast, our theorem provides a simple approximate formula for distances ‖f̃(x) - f̃(y)‖.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

We study a clustering problem where the goal is to maximize the coverage of the input points by k chosen centers. Specifically, given a set of n points P ⊆ ℝ^d, the goal is to pick k centers C ⊆ ℝ^d that maximize the service ∑_{p∈P}φ(𝖽(p,C)) to the points P, where 𝖽(p,C) is the distance of p to its nearest center in C, and φ is a non-increasing service function φ: ℝ+ → ℝ+. This includes problems of placing k base stations as to maximize the total bandwidth to the clients - indeed, the closer the client is to its nearest base station, the more data it can send/receive, and the target is to place k base stations so that the total bandwidth is maximized. We provide an n^{ε^-O(d)} time algorithm for this problem that achieves a (1-ε)-approximation. Notably, the runtime does not depend on the parameter k and it works for an arbitrary non-increasing service function φ: ℝ+ → ℝ+.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Proving hardness of approximation is a major challenge in the field of fine-grained complexity and conditional lower bounds in P.
How well can the Longest Common Subsequence (LCS) or the Edit Distance be approximated by an algorithm that runs in near-linear time?
In this paper, we make progress towards answering these questions.
We introduce a framework that exhibits barriers for truly subquadratic and deterministic algorithms with good approximation guarantees.
Our framework highlights a novel connection between deterministic approximation algorithms for natural problems in P and circuit lower bounds.
In particular, we discover a curious connection of the following form:
if there exists a \delta>0 such that for all \eps>0 there is a deterministic (1+\eps)-approximation algorithm for LCS on two sequences of length n over an alphabet of size n^{o(1)} that runs in O(n^{2-\delta}) time, then a certain plausible hypothesis is refuted, and the class E^NP does not have non-uniform linear size Valiant Series-Parallel circuits.
Thus, designing a "truly subquadratic PTAS" for LCS is as hard as resolving an old open question in complexity theory.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

We show that the Hausdorff metric over constant-size pointsets in constant-dimensional Euclidean space admits an embedding into constant-dimensional l_{infinity} space with constant distortion. More specifically for any s,d>=1, we obtain an embedding of the Hausdorff metric over pointsets of size s in d-dimensional Euclidean space, into l_{\infinity}^{s^{O(s+d)}} with distortion s^{O(s+d)}. We remark that any metric space M admits an isometric embedding into l_{infinity} with dimension proportional to the size of M. In contrast, we obtain an embedding of a space of infinite size into constant-dimensional l_{infinity}.
We further improve the distortion and dimension trade-offs by considering probabilistic embeddings of the snowflake version of the Hausdorff metric. For the case of pointsets of size s in the real line of bounded resolution, we obtain a probabilistic embedding into l_1^{O(s*log(s()} with distortion O(s).

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Given n weighted points (positive or negative) in d dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains?
The best known algorithm for this problem is based on a reduction to a related problem, the Weighted Depth problem [Chan, FOCS, 2013], and runs in time O(n^d). It was conjectured [Barbay et al., CCCG, 2013] that this runtime is tight up to subpolynomial factors. We answer this conjecture affirmatively by providing a matching conditional lower bound. We also provide conditional lower bounds for the special case when points are arranged in a grid (a well studied problem known as Maximum Subarray problem) as well as for other related problems.
All our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially optimal.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis (A. Ambainis, 1999), and shows that van Dam's oracle interrogation (W. van Dam, 1998) is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.

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)

Copy BibTex To Clipboard

@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} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail