Collection Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme
Organizer(s)
Date(s)
13/05/2024
Rectangle inequalities for data structure lower bounds
By Yitong Yin
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.
