55 citations · 62 across the 8 of their papers we have counts for
12 papers · 1 filter
Fast Distance Oracles for Any Symmetric Norm
Yichuan Deng, Zhao Song, Omri Weinstein +1
In the Distance Oracle problem, the goal is to preprocess vectors in a -dimensional metric space into a cheap data st…
Faster Dynamic Matrix Inverse for Faster LPs
Shunhua Jiang, Zhao Song, Omri Weinstein +1
Motivated by recent Linear Programming solvers, we design dynamic data structures for maintaining the inverse of an real matrix under updates, with…
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…