Oblivious Median Slope Selection

Thore Thießen, Jan Vahrenhold

We study the median slope selection problem in the oblivious RAM model. In this model memory accesses have to be independent of the data processed, i.e., an adversary cannot use ob…