Abstract
We introduce semidirect 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 semidirect sum framework, we prove an information lower bound on capproximate Nearest Neighbor (ANN) under l_infty which implies that the algorithm of [Indyk, 2001] for capproximate 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.
BibTeX  Entry
@InProceedings{braverman_et_al:LIPIcs:2018:9410,
author = {Mark Braverman and Young Kun Ko},
title = {{SemiDirect Sum Theorem and Nearest Neighbor under l_infty}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {6:16:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9410},
URN = {urn:nbn:de:0030drops94101},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.6},
annote = {Keywords: Asymmetric Communication Lower Bound, Data Structure Lower Bound, Nearest Neighbor Search}
}
Keywords: 

Asymmetric Communication Lower Bound, Data Structure Lower Bound, Nearest Neighbor Search 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) 
Issue Date: 

2018 
Date of publication: 

13.08.2018 