Semi-Direct Sum Theorem and Nearest Neighbor under ℓ

Mark Braverman, Young Kun Ko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce semi-direct sum theorem as a framework for proving asymmetric communication lower bounds for the functions of the form Vn i=1 f(x, yi). Utilizing tools developed in proving direct sum W theorem for information complexity, we show that if the function is of the form Vn i=1 f(x, yi) where Alice is given x and Bob is given yi's, it suffices to prove a lower bound for a single f(x, yi). This opens a new avenue of attack other than the conventional combinatorial technique (i.e. "richness lemma" from [12]) for proving randomized lower bounds for asymmetric communication for functions of such form. As the main technical result and an application of semi-direct sum framework, we prove an information lower bound on c-approximate Nearest Neighbor (ANN) under ℓ which implies that the algorithm of [9] for c-approximate Nearest Neighbor under ℓ is optimal even under randomization for both decision tree and cell probe data structure model (under certain parameter assumption for the latter). In particular, this shows that randomization cannot improve [9] under decision tree model. Previously only a deterministic lower bound was known by [1] and randomized lower bound for cell probe model by [10]. We suspect further applications of our framework in exhibiting randomized asymmetric communication lower bounds for big data applications.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
EditorsEric Blais, Jose D. P. Rolim, David Steurer, Klaus Jansen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770859
DOIs
StatePublished - Aug 1 2018
Event21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018 - Princeton, United States
Duration: Aug 20 2018Aug 22 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume116
ISSN (Print)1868-8969

Other

Other21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
CountryUnited States
CityPrinceton
Period8/20/188/22/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Asymmetric Communication Lower Bound
  • Data Structure Lower Bound
  • Nearest Neighbor Search

Fingerprint Dive into the research topics of 'Semi-Direct Sum Theorem and Nearest Neighbor under ℓ<sub>∞</sub>'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., & Ko, Y. K. (2018). Semi-Direct Sum Theorem and Nearest Neighbor under ℓ In E. Blais, J. D. P. Rolim, D. Steurer, & K. Jansen (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018 [6] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 116). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.6