# Semi-Direct Sum Theorem and Nearest Neighbor under l_infty

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

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr15j8t
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorKo, Young K-
dc.date.accessioned2021-10-08T19:44:50Z-
dc.date.available2021-10-08T19:44:50Z-
dc.date.issued2018en_US
dc.identifier.citationBraverman, 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.6en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr15j8t-
dc.description.abstractWe 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.en_US
dc.format.extent6:1 - 6:17en_US
dc.language.isoen_USen_US
dc.relation.ispartofApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM)en_US
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics, LIPIcs;-
dc.rightsFinal published version. This is an open access article.en_US
dc.titleSemi-Direct Sum Theorem and Nearest Neighbor under l_inftyen_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.APPROX-RANDOM.2018.6-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat