Skip to main content

Semi-Direct Sum Theorem and Nearest Neighbor under l_infty

Author(s): Braverman, Mark; Ko, Young K

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr15j8t
Abstract: We introduce semi-direct sum theorem as a framework for proving asymmetric communication lower bounds for the functions of the form V_{i=1}^n f(x,y_i). Utilizing tools developed in proving direct sum theorem for information complexity, we show that if the function is of the form V_{i=1}^n f(x,y_i) where Alice is given x and Bob is given y_i's, it suffices to prove a lower bound for a single f(x,y_i). This opens a new avenue of attack other than the conventional combinatorial technique (i.e. "richness lemma" from [Miltersen et al., 1995]) 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 l_infty which implies that the algorithm of [Indyk, 2001] for c-approximate Nearest Neighbor under l_infty 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 [Indyk, 2001] under decision tree model. Previously only a deterministic lower bound was known by [Andoni et al., 2008] and randomized lower bound for cell probe model by [Kapralov and Panigrahy, 2012]. We suspect further applications of our framework in exhibiting randomized asymmetric communication lower bounds for big data applications.
Publication Date: 2018
Citation: Braverman, Mark, and Young Kun Ko. "Semi-Direct Sum Theorem and Nearest Neighbor under l_infty." Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) 116 (2018): pp. 6:1-6:17. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.6
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.6
ISSN: 1868-8969
Pages: 6:1 - 6:17
Type of Material: Conference Article
Series/Report no.: Leibniz International Proceedings in Informatics, LIPIcs;
Journal/Proceeding Title: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM)
Version: Final published version. This is an open access article.



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.