## Abstract

We introduce semi-direct sum theorem as a framework for proving asymmetric communication lower bounds for the functions of the form V^{n} _{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 V^{n} _{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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018 |

Editors | Eric Blais, Jose D. P. Rolim, David Steurer, Klaus Jansen |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Print) | 9783959770859 |

DOIs | |

State | Published - Aug 1 2018 |

Event | 21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018 - Princeton, United States Duration: Aug 20 2018 → Aug 22 2018 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 116 |

ISSN (Print) | 1868-8969 |

### Other

Other | 21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018 |
---|---|

Country/Territory | United States |

City | Princeton |

Period | 8/20/18 → 8/22/18 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Asymmetric Communication Lower Bound
- Data Structure Lower Bound
- Nearest Neighbor Search