Skip to content

Mihai Pătraşcu 1982–2012

June 8, 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.

Curriculum Vitae

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:

He also did a series on interesting Informatics Olympiad problems beginning here, and one can find much else to ponder on his blog.

Open Problems

Pătraşcu’s joint FOCS 2004 paper, as described by Mohammad Taghi Hajiaghayi in Lance Fortnow’s item, constructed {O(\log\log n)}-competitive online binary search trees where {O(\log n)} had previously been best known. This was the first major progress in two decades on Robert Tarjan and Daniel Sleator’s conjecture that {O(1)}-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.

[fixed typos]

16 Comments leave one →
  1. June 8, 2012 8:57 am

    Two typos:

    1) “Motocicleta” instead of “Motocliceta”.

    2) Mihai was involved in the Informatics Olympiads, not the Mathematics Olympiads (or was he involved in both?). The 2011 post you link to is the website of the 2011 Balkan Olympiad in Informatics (not Mathematics).

  2. June 8, 2012 9:25 am

    May he rest in peace.

  3. kamouna permalink
    June 9, 2012 12:12 am

    R.I.P. may God bless his soul. Condelences go to his wife, family and friends.

    Rafee Kamouna.

  4. FLORINA permalink
    June 12, 2012 1:34 am


  5. Emilia permalink
    June 12, 2012 4:12 pm

    Dumnezeu sa-l odihneasca!!!

    • June 12, 2012 11:15 pm

      The last two entries are Romanian for “[May] God grant him rest [eternal].”

      • June 16, 2012 10:03 am

        It’s the equivalent of RIP.

  6. June 12, 2012 11:03 pm

    I can add a personal note from the week of April 8–15 in which I wrote the post featuring Mihai which appeared on the 14th. That Wednesday, the 11th, I had not yet wished Happy Easter to a friend and chess blogger who is of Greek extraction. I found on the official forum of the chess program Rybka a post giving the Easter response in Greek, and copied it to the friend saying how nice I could mouse-copy it from there. As the Rybka post also notes, the Eastern Orthodox churches were observing Easter the following Sunday, the 15th.

    On that Friday I e-mailed Mihai to let him know that a post on his paper with Mikkel Thorup was coming, and to ask a last-minute question. Only now do I know why that and a later e-mail to him saying the post was out had no reply. On the Sunday or shortly afterward I saw Mihai’s April 15 Easter post, now the second-last on his blog, and smiled at the coincidence of seeing the Easter greeting in Greek again, though I did not tell my friend. I take that as having been the reply.

  7. June 21, 2012 1:43 am

    Reblogged this on ramblingbog.

  8. June 21, 2012 2:10 am

    Update: A memorial website has been set up, to which people can contrinute in various ways.

    Should be:
    Update: A memorial website has been set up, to which people can contribute in various ways.

    • June 21, 2012 11:17 am

      Thanks! I don’t know why certain typos are invisible…

  9. June 21, 2012 8:07 am

    Reblogged this on Higher Order Thoughts and commented:
    Sadly, I found out about him after he passed away…

  10. June 22, 2012 4:17 pm

    My deepest condolences. He is a great role-model.


  1. Hashtables and the Library of Utopia « Pink Iguana

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s