Mihai Pătraşcu 1982–2012
A pathbreaking researcher taken too soon from us
Mihai Pătraşcu passed away on Tuesday of brain cancer, having not yet reached age 30. We, Dick and Ken, did not know about his year-and-a-half battle until yesterday, even though we had featured him in April.
Today we join all those expressing grief and shock and condolences, and seek to further what some are doing to observe his work and life.
The most common professional tributes are that Pătraşcu “revolutionized the field of data structures,” which “might have to wait another couple decades for someone to breathe such life into the field again.” There are also moving personal stories showing his engagement in life and in the community of our field, several as comments in Michael Mitzenmacher’s tribute.
Indeed Mihai was a fellow theoretical computer science blogger. His weblog carried both the general title “Informatics Weekly” reflected in its URL, and the displayed title “Webdiarios de Motocicleta”—adding “Web” to the Spanish title of Che Guevara’s famous memoir. His first post in July 2007 was titled “Ars Poetica” and related that he too rode an old motorcycle and sought to revolutionize.
The CV at his MIT page was updated last month to show his 2012 Presburger Award, joint with Venkatesan Guruswami. As related by Lance Fortnow, Mihai was conveyed two weeks ago in his wheelchair to STOC where he was introduced to a filled room as co-winner of this EATCS award, in what Lance called “the most emotional moment I have ever seen at an academic conference.”
Mihai had also happily announced his award in his May 6th entry, the last on his blog. None of the 19 congratulatory comments mentioned his illness, and I (Ken) find not a breath of it on his blog at all.
CV stands for curriculum vitae, which literally in Latin means “the course of life.” Thus Mihai did not put all of the course of his life on his blog—and I could write pages on what’s been happening in mine just while writing these words.
But one thing he put there was the beginning of a curriculum in the ordinary academic sense—a course of key things one can learn to get into his mind on data structures. Accordingly we index some of these posts, to let him speak the subject he loved in his own words:
- Probability Moments, Jan. 26, 2010.
- Basic Hashtables, Jan. 27, 2010.
- Better Guarantees for Chaining and Linear Probing, Feb. 2, 2010.
- Cuckoo Hashing, also Feb. 2, 2010.
- Prefix-Free Codes, Part 1 of a post on his work, June 2, 2010.
- Representing a Vector, Part 2, also June 2, 2010.
- A taxonomy of range-query problems, Aug. 4, 2010.
He also did a series on interesting Informatics Olympiad problems beginning here, and one can find much else to ponder on his blog.
Pătraşcu’s joint FOCS 2004 paper, as described by Mohammad Taghi Hajiaghayi in Lance Fortnow’s item, constructed -competitive online binary search trees where had previously been best known. This was the first major progress in two decades on Robert Tarjan and Daniel Sleator’s conjecture that -competitivity was possible. Is it?
Our condolences go out to his wife Mira, his other family, and his many friends.
Update: A memorial website has been set up, to which people can contribute in various ways.