AT&T Labs Research — Leading Invention, Driving Innovation

Mihai Pătraşcu (1982-2012) 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, and later served as chair for the Central European Olympiad in Informatics, 2009. In 2008, he received the Machtey Award for the best student paper at the Symposium on Foundations of Computer Science. In 2012, while a Senior Member of Technical Staff at AT&T Labs - Research, he  received the Presburger Award from the European Association for Theoretical Computer Science, for breaking “many old barriers on fundamental data structure problems, not only revitalizing but also revolutionizing a field that was almost silent for over a decade.”

Additional papers can be found on his MIT website and on his Wikipedia page.

(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. }

(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.

{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_u$ be the time to insert an edge and $t_q$ be the query time. For $t_u = Omega(t_q)$, the problem is equivalent to the well-understood emph{union--find} problem: $proc{InsertEdge}(s,t)$ can be implemented by $proc{Union}(proc{Find}(s), proc{Find}(t))$. This gives worst-case time $t_u = t_q = O(lg n / lglg n)$ and amortized $t_u = t_q = O(alpha(n))$. By contrast, we show that if $t_u = o(lg n / lglg n)$, the query time explodes to $t_q ge n^{1-o(1)}$. In other words, if the data structure doesn't have time to find the roots of each disjoint set (tree) during edge insertion, there is no effective way to organize the information! For amortized complexity, we demonstrate a new inverse-Ackermann type trade-off in the regime $t_u = o(t_q)$. A similar lower bound is given for fully dynamic connectivity, where an update time of $o(lg n)$ forces the query time to be $n^{1-o(1)}$. This lower bound allows for amortization and Las Vegas randomization, and comes close to the known $O(lg n cdot (lglg n)^{O(1)})$ upper bound. }

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