TY - GEN
T1 - Semi-Direct Sum Theorem and Nearest Neighbor under ℓ∞
AU - Braverman, Mark
AU - Ko, Young Kun
N1 - Funding Information:
Research supported in part by an NSF Awards, DMS-1128155, CCF-1525342, and CCF-1149888, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
PY - 2018/8/1
Y1 - 2018/8/1
N2 - 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.
AB - 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.
KW - Asymmetric Communication Lower Bound
KW - Data Structure Lower Bound
KW - Nearest Neighbor Search
UR - http://www.scopus.com/inward/record.url?scp=85052433577&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052433577&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2018.6
DO - 10.4230/LIPIcs.APPROX-RANDOM.2018.6
M3 - Conference contribution
AN - SCOPUS:85052433577
SN - 9783959770859
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
A2 - Blais, Eric
A2 - Rolim, Jose D. P.
A2 - Steurer, David
A2 - Jansen, Klaus
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
Y2 - 20 August 2018 through 22 August 2018
ER -