39 citations · 87 across the 16 of their papers we have counts for
14 papers · 1 filter
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}…
Don't Rush into a Union: Take Time to Find Your Roots
Mihai Patrascu, Mikkel Thorup
We present a new threshold phenomenon in data structure lower bounds where slightly reduced update times lead to exploding query times. Consider incremental connectivity, letting t…
The Power of Simple Tabulation Hashing
Mihai Patrascu, Mikkel Thorup
Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here w…
Unifying the Landscape of Cell-Probe Lower Bounds
Mihai Patrascu
We show that a large fraction of the data-structure lower bounds known today in fact follow by reduction from the communication complexity of lopsided (asymmetric) set disjointness…
Transdichotomous Results in Computational Geometry, II: Offline Search
Timothy M. Chan, Mihai Patrascu
We reexamine fundamental problems from computational geometry in the word RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for…
A Lower Bound for Succinct Rank Queries
Mihai Patrascu
The rank problem in succinct data structures asks to preprocess an array A[1..n] of bits into a data structure using as close to n bits as possible, and answer queries of the form…
Dynamic Connectivity: Connecting to Networks and Geometry
Timothy M. Chan, Mihai Patrascu, Liam Roditty
Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an…
Radix Sorting With No Extra Space
Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
It is well known that n integers in the range [1,n^c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,U] can be sorted in…
On Dynamic Range Reporting in One Dimension
Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu
We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching i…
Logarithmic Lower Bounds in the Cell-Probe Model
Mihai Patrascu, Erik D. Demaine
We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Omega(lg n) lower bound per op…