39 citations · 87 across the 16 of their papers we have counts for
18 papers
Finding the Median (Obliviously) with Bounded Space
Paul Beame, Vincent Liew, Mihai Pǎtraşcu
We prove that any oblivious algorithm using space to find the median of a list of integers from requires time . This bound also applies to…
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search
Mihai Patrascu, Mikkel Thorup
We present a data structure representing a dynamic set S of w-bit integers on a w-bit word RAM. With |S|=n and w > log n and space O(n), we support the following standard operation…
On the k-Independence Required by Linear Probing and Minwise Independence
Mikkel Thorup
We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of [Pagh et al. STOC'07]. More precisely, we const…
Necklaces, Convolutions, and X+Y
David Bremner, Timothy M. Chan, Erik D. Demaine +6
We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alig…
Picture-Hanging Puzzles
Erik D. Demaine, Martin L. Demaine, Yair N. Minsky +3
We show how to hang a picture by wrapping rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and…
Using Hashing to Solve the Dictionary Problem (In External Memory)
John Iacono, Mihai Pǎtraşcu
We consider the dictionary problem in external memory and improve the update time of the well-known buffer tree by roughly a logarithmic factor. For any λ>= max {lg lg n, log_{M/B}…