55 citations · 62 across the 9 of their papers we have counts for
4 papers · 1 filter
Settling the relationship between Wilber's bounds for dynamic optimality
Victor Lecomte, Omri Weinstein
In FOCS 1986, Wilber proposed two combinatorial lower bounds on the operational cost of any binary search tree (BST) for a given access sequence . Both bounds play a c…
An Adaptive Step Toward the Multiphase Conjecture
Young Kun Ko, Omri Weinstein
In 2010, Pǎtraşcu proposed the following three-phase dynamic problem, as a candidate for proving polynomial lower bounds on the operational time of dynamic data structures: I: Prep…
How to Store a Random Walk
Emanuele Viola, Omri Weinstein, Huacheng Yu
Motivated by storage applications, we study the following data structure problem: An encoder wishes to store a collection of jointly-distributed files $\overline{X}:=(X_1,X_2,\ldot…
Lower Bounds for Oblivious Near-Neighbor Search
Kasper Green Larsen, Tal Malkin, Omri Weinstein +1
We prove an lower bound on the dynamic cell-probe complexity of statistically approximate-near-neighbor search () over…