TY - GEN
T1 - Semi-Direct Sum Theorem and Nearest Neighbor under ℓ∞
AU - Braverman, Mark
AU - Ko, Young Kun
N1 - Publisher Copyright:
© 2018 Aditya Bhaskara and Srivatsan Kumar.
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 -