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 ) 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  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  under decision tree model. Previously only a deterministic lower bound was known by  and randomized lower bound for cell probe model by . We suspect further applications of our framework in exhibiting randomized asymmetric communication lower bounds for big data applications.