AT&T Labs Research — Leading Invention, Driving Innovation

Mihai Pătrascu is a Senior Member of Technical Staff at AT&T Labs-Research. Mihai obtained a PhD (2008) and B.S. (2006) from MIT. After MIT, he spent a year at IBM Almaden on the Raviv Memorial Fellowship. Mihai received the Best Student Paper awards at FOCS'08 and ICALP'05, and the CRA Outstanding Undergraduate Research Award in 2005. During his high school studies in Romania, Mihai earned a number of medals in computer olympiads. He later served as chair for the Central European Olympiad in Informatics, 2009.

Additional papers can be found on at his MIT website.

(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of teh ACM/SIAM Symposium on Discrete Algorithms (SODA), 2012 , 2012-01-17.

{We consider the dictionary problem in external memory and improve the update time of the well-known emph{buffer tree} by roughly a logarithmic factor. For any $lambda ge max { lglg n, log_{M/B} (n/B) }$, we can support updates in time $O(frac{lambda}{B})$ and queries in time $O(log_lambda n)$. We also present a lower bound in the cell-probe model showing that our data structure is optimal. In the RAM, hash tables have been use to solve the dictionary problem faster than binary search for more than half a century. By contrast, our data structure is the first to beat the comparison barrier in external memory. Ours is also the first data structure to depart convincingly from the emph{indivisibility} paradigm. }

(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of ACM STOC'11. , 2011-06-06.

{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 we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting of $c$ characters. We initialize $c$ tables $T_1, dots, T_c$ mapping characters to random hash code. A key $x=(x_1, dots, x_q)$ is hashed to $T_1[x_1] oplus cdots oplus T_c[x_c]$, where $oplus$ denotes xor. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing. }

(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Symposium on Computational Geometry , 2011-06-13.

{We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model: * We present two data structures for 2-d orthogonal range emptiness. The first achieves $O(nlglg n)$ space and $O(lglg n)$ query time, assuming that the $n$ given points are in rank space. This improves the previous results by Alstrup, Brodal, and Rauhe (FOCS'00), with $O(nlg^eps n)$ space and $O(lglg n)$ query time, or with $O(nlglg n)$ space and $O(lg^2lg n)$ query time. Our second data structure uses $O(n)$ space and answers queries in $O(lg^eps n)$ time. The best previous $O(n)$-space data structure, due to Nekrich (WADS'07), answers queries in $O(lg n/lg lg n)$ time. * We give a data structure for 3-d orthogonal range reporting with $O(nlg^{1+eps} n)$ space and $O(lglg n + k)$ query time for points in rank space, for any constant $eps>0$. This improves the previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with $O(nlg^3 n)$ space and $O(lglg n + k)$ query time, or with $O(nlg^{1+eps}n)$ space and $O(lg^2lg n + k)$ query time. Consequently, we obtain improved upper bounds for orthogonal range reporting in all constant dimensions above~3. Our approach also leads to a new data structure for 2-d orthogonal range minimum queries with $O(nlg^eps n)$ space and $O(lglg n)$ query time for points in rank space. * We give a randomized algorithm for 4-d emph{offline} dominance range reporting/emptiness with running time $O(nlog n)$ plus the output size. This resolves two open problems (both appeared in Preparata and Shamos' seminal book): **(a)** given a set of $n$ axis-aligned rectangles in the plane, we can report all $k$ enclosure pairs (i.e., pairs $(r_1,r_2)$ where rectangle $r_1$ completely encloses rectangle $r_2$) in $O(nlg n + k)$ expected time; **(b)** given a set of $n$ points in 4-d, we can find all maximal points (points not dominated by any other points) in $O(nlg n)$ expected time. The most recent previous development on (a) was reported back in SoCG'95 by Gupta, Janardan, Smid, and Dasgupta, whose main result was an $O([nlg n + k]lglg n)$ algorithm. The best previous result on (b) was an $O(nlg nlglg n)$ algorithm due to Gabow, Bentley, and Tarjan---from STOC'84! As a consequence, we also obtain the current-record time bound for the maxima problem in all constant dimensions above~4. }

Awards
Presburger Award, 2012. For contributing fundamental results on lower bounds for data structures.