Mihai Pătraşcu (1982-2012)

Yesterday brought the tragic news that Mihai Pătraşcu—who revolutionized the field of data structures since he burst onto the scene a decade ago—has passed away at the age of 29, after a year-and-a-half-long battle with brain cancer.  Mihai was not only an outstanding researcher but a fun-loving, larger-than-life personality in the computer science theory community.  For more information, see Lance and Bill’s or Michael Mitzenmacher’s blogs.

Mihai was an MIT CS PhD student (advised by Erik Demaine), who worked on the same floor as me for the first couple years I was here.  I’m still in shock over his loss—I hadn’t even known about the cancer before yesterday.   Mihai and I had pretty big disagreements, mostly over the viability of quantum computing, the “technical” versus “conceptual” theory debate, various things he wrote on his blog and various things I wrote on mine.  But it seems terribly stupid now to have let this stuff get in the way of collegiality.  I feel guilty for not trying to mend bridges with him when I had the chance.

Rest in peace, Mihai.

13 Responses to “Mihai Pătraşcu (1982-2012)”

  1. Jonathan Shewchuk Says:

    I am shocked.

    When I was course scheduling officer for the Berkeley CS department, Mihai was kind enough to volunteer to step in to finish teaching CS 172 (Computability and Complexity) when the original instructor had to leave for medical reasons. He certainly didn’t have to do that, and I and the original instructor are grateful.

    But what impressed me most was his o(n log n)-time Voronoi diagram algorithm. He told me later that I had inspired him by posing it as an open problem that could probably be solved, and I am honored to have played that tiny role in his successes.

  2. Mihai Pătraşcu 1982–2012 « Gödel’s Lost Letter and P=NP Says:

    […] most common professional tributes are that Pătraşcu “revolutionized the field of data structures,” which “might have to wait another couple decades for […]

  3. Mohsen Says:

    I don’t know why the news shocked me. I even didn’t know him at all and never seen him before.
    Maybe just feeling guilty for being approximately the same age, contributing nothing to the world and still being alive!

  4. Scott Says:

    Mohsen: Instead of feeling guilty, feel lucky to be alive, and motivated to (in the worn-down saying that might as well have been invented for this case) “live each day like it was your last.”

  5. Bram Cohen Says:

    I couldn’t help but be curious about what the controversies around Mihai were, and some reading seems to indicate that he was an outspoken person with an ego which matched his accomplishments, which doesn’t seem like such a horribly bad thing.

  6. Philip White Says:

    I never communicated with him and hadn’t heard of him until now, but after I read this post I did a little research. Looking at his blog, it looks like he had some pointed opinions about complexity theory:


    He accuses computer scientists of having groupthink for being part of a “choir” that praises Ryan Williams’ result in a way that he considers over the top. Scott’s blog responds to this sort of criticism (without mentioning anyone in particular) here:


    I’m not qualified to judge Williams’ result’s significance, but Patrascu’s point doesn’t sound as “out there” as some bloggers have made it sound (nearly every blog notes his “opinionated” nature.) There’s a bit of hushed backtracking on many of the blogs I’ve looked at.

    I guess it’s considered a bit risky to be so critical; perhaps he was expected to be more positive. I think he sounds bold and insightful; questioning the values/wisdom of the community you are a member of takes a bit of courage, even if I don’t know if he’s right.

    Anyway, I think he sounds reasonable, and though I didn’t know a thing about him, it sounds like he was a pretty sharp/interesting guy. It’s worth noting that Grigori Perelman, the man who solved the Poincare conjecture, has also made similar (actually much harsher) claims about mathematicians and conformity.

  7. Peter Sheldrick Says:

    This is tragic. It is a testament to his personality that being told one day that death is almost inevitable within 1-2 years didn’t rattle him enough even to stop blogging (as opposed to panic attacks etc.).

    @Philip White, as you bring up Mr. Perelman has an accomplished yet combative mathematician – recently i noticed that he refused the EMS prize in 1996. Of course him refusing both the Fields Medal and Millenium prize was one of the most spectacular events in Math from the past few years. But still it shocked me that he refused a prize that in 1996 was accepted by, among others, Jiri Matousek and Tim Gowers.

  8. Tinker Says:

    “He accuses computer scientists of having groupthink for being part of a “choir” that praises Ryan Williams’ result in a way that he considers over the top. ”

    I didn’t think the criticism was that the praise was “over the top” per se, but that people were simply repeating this praise because someone else had said it.

    In other words, if 10 people each read the paper independently and each come to the conclusion that the result is amazing, then go ahead and say how great it is publicly. This could be accompanied by some actual evidence that the reader read the paper and why they think the result is so great.

    This is in contrast to what many people do on blogs which is repeat the fact that something is a breakthrough purely because someone else said so or because a paper got an award, etc. Many great papers have many admirers, but each genuine admirer has a reason that they think the paper has a great idea.

    After reading all of the blogs, I thought that Ryan’s result is considered a “breakthrough” but admittedly had no clue why. This is not the way things should be.

    If you look at what Mihai says, he does not say that the paper is not great and he does not criticize the paper. Note that knowing Mihai, he would have criticized the paper if he had reason to.

    I think what he meant is that most people who are saying that the paper *is* great likely have no idea why they are saying this, which is group think. I.e. it might not be intuitive that one can criticize/disagree with the reasons behind a behaviour/outcome even if they agree with that outcome.

  9. Philip White Says:

    @Tinker #8. Thanks for clarifying his point. I commented on it largely because it’s related to something I find fascinating–namely the notion of “social proof,” which is related to groupthink and is basically the idea that if a lot of people think something is good, others start to believe it’s good, too, uncritically, based on no evidence other than the “everybody’s doing/thinking it” factor. (There are also some interesting parallels between group think and game theory, such as the notion of unilateral defection from the group opinion.)

    It’s interesting, because I don’t think complexity theory is the only area with such a “choir.” I’m not even sure it’s such a bad thing; speaking of game theory and Nash equilibria, I will admit to being impressed with John Nash’s result in spite of my complete lack of insight into what Kakutani’s fixed point theorem really is. Indeed, most people consider Einstein, Nash, Turing, Godel, von Neumann, etc., etc., to be geniuses without the faintest clue of why they were so smart.

  10. Tinker Says:

    @philip white: I want to be clear that what I wrote was my interpretation of Mihai’s blog post, what I think he meant.

    “I will admit to being impressed with John Nash’s result in spite of my complete lack of insight into what Kakutani’s fixed point theorem really is.”

    I think this is somewhat different from group think: whether or not you completely understand Nash’s theorem, you appear to be saying that !you! were impressed by the theorem when you heard of it. You didn’t hear of the theorem, have no clue what it meant enough to be impressed by it, and then go tell everyone you had heard this amazing theorem. I think you can have the intuition that something is interesting or amazing without fully understanding it. But if it is !your! opinion, your feelings, then it is (hopefully) not groupthink.

  11. Hopefully Anonymous Says:

    A mea culpa like this greatly impresses me with regards to your character, Prof. Aaronson. To be right, to be wrong, to be higher status, to be lower status, to have satisfactions, and to have regrets, without militantly wanting only that which glorifies oneself. We need a world of people with that kind of ego flexibility to make our hospice our heaven.

  12. Hopefully Anonymous Says:

    I skimmed some of his posts as an illiterate nonexpert. His personality really jumps out at you in a good way. He seems, like you Prof. Aaronson, like a great example of how to combine unusual (and perhaps inherently esoteric) talent with popularly accessible charm and good humor.

    If you were a bit put off, I wonder if in part because he seemed to have a lot of your best traits. I could see myself being like “I’m supposed to be the funny, good-natured theoretical computer science in the group”.

  13. Hopefully Anonymous Says:

    I’ve contributed nothing either, and I’m quite a bit older. Just give 100% each day towards making our patient administered hospice reality the best it can be. No one’s solving the problem that we’re all going to die and the human species will extinct. But we can make this reality as humane experience as possible for the temporarily living.