Appears in collection : 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

The richness lemma is a classic rectangle-based technique for asymmetric communication complexity and cell-probe lower bounds. The technique was enhanced by the Patrascu-Thorup’s direct-sum approach to prove higher cell-probe lower bounds. In this talk, I will give an improved richness lemma which generalizes the previous ones and may support even higher cell-probe lower bounds. Combined with the isoperimetric inequalities, we give an Ω(d) cell-probe lower bound for the nearest neighbor search problem when the data structure is of linear size.