4 papers
The Case for External Graph Sketching
Michael A. Bender, Martín Farach-Colton, Riko Jacob +3
Algorithms in the data stream model use space to compute some property of an input of size , and many of these algorithms are implemented and used in practice. H…
An Optimal Randomized Algorithm for Finding the Saddlepoint
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A \emph{saddlepoint} of an matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the \emph{value} of a two-player zero-sum…
An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio
Mayank Goswami, Riko Jacob
The problem of sorting with priced information was introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparison…
Finding the saddlepoint faster than sorting
Justin Dallant, Frederik Haagensen, Riko Jacob +2
A saddlepoint of an matrix is an entry of that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding…