8 citations · 14 across the 3 of their papers we have counts for
3 papers
cs.DS2014★ 4 cited
New Techniques and Tighter Bounds for Local Computation Algorithms
Omer Reingold, Shai Vardi
Given an input , and a search problem , local computation algorithms (LCAs) implement access to specified locations of in a legal output , using polylogarithm…
cs.DS2014★ 2 cited
The secretary returns
Shai Vardi
In the online random-arrival model, an algorithm receives a sequence of n requests that arrive in a random order. The algorithm is expected to make an irrevocable decision with reg…
cs.DS2012★ 8 cited
Converting online algorithms to local computation algorithms
Yishay Mansour, Aviad Rubinstein, Shai Vardi +1
We propose a general method for converting online algorithms to local computation algorithms by selecting a random permutation of the input, and simulating running the online algor…