A Lower Bound for Succinct Rank Queries (2009)
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 rank(k) =...
Dynamic Connectivity: Connecting to Networks and Geometry (2008)
Chan, Timothy M., Patrascu, Mihai, Roditty, Liam
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 undirected graph,...
Farey Statistics in Time n^{2/3} and Counting Primitive Lattice Points in Polygons (2007)
We present algorithms for computing ranks and order statistics in the Farey sequence, taking time O (n^{2/3}). This improves on the recent algorithms of Pawlewicz [European Symp. Alg. 2007], running...
Radix Sorting With No Extra Space (2007)
Franceschini, Gianni, Muthukrishnan, S., Patrascu, Mihai
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 O(n sqrt{loglog n})...
Time-Space Trade-Offs for Predecessor Search (2006)
Patrascu, Mihai, Thorup, Mikkel
We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting...
De Dictionariis Dynamicis Pauco Spatio Utentibus (2005)
Demaine, Erik D., Pagh, Rasmus, Patrascu, Mihai
We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, up to constant factors, subject to insertions and deletions, and subject to supporting perfect-hashing queries...
Logarithmic Lower Bounds in the Cell-Probe Model (2005)
Patrascu, Mihai, Demaine, Erik D.
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 operation for several...
On Dynamic Range Reporting in One Dimension (2005)
Mortensen, Christian Worm, Pagh, Rasmus, Patrascu, Mihai
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 is a natural and...