Skip to content

Congrats to Goldwasser and Micali

Shafi Goldwasser and Silvio Micali won the Turing Award recently.  Crypto theory is both incredibly interesting and useful, and Goldwasser and Micali had a hand in a ton of the foundational papers.  I’m proud to say Ive had both of them as instructors and actually knew Silvio pretty well (TA’ed for a class he taught, in addition to taking two of his classes).  He’s easily one of the most amusing instructors I’ve had, and many of my friends will tell you the same.  He’s full of humor, wisdom, ideas, Italian blood, and other good things.  In his honor, I’ll write a post which tries to teach some cryptography.

I’m not going to try to explain any of the things Goldwasser and Micali came up with.  I’d just be repeating Micali’s lectures, but doing it badly.  Instead, I’m going to try to illustrate the idea of bootstrapping in Gentry’s construction of homomorphic encryption.  I chose this because:

  • It was a huge breakthrough in cryptography
  • It can be well-illustrated, to a non-cryptographer, in my opinion.
  • It is one of my favorite proof ideas.
  • I haven’t seen it explained in a super nice way elsewhere.
  • I have presented on this topic in the past, in a presentation skills class at MIT, with similar aim.

My goal is to illustrate the way Micali did, but to an even less technical audience.

Read more…


Thoughts on getting older, and post-school life

I recently graduated from college and became a “real person”.  I also no longer feel like a teenager.  Here are some initial thoughts on aging and post-school life.  None if this is particularly surprising, though I wonder if it would have been surprising to past me.

  1. The material I learned in college seems like it was mostly useless.  This is worsened by the fact that I learned largely theory, and I suspect it’s much less true in general.  However, I suspect you can learn all the useful things in college in much less expensive settings.  Nevertheless, it seems to me that MIT was plausibly a reasonable use of money.  I met extremely useful people, learned useful non-academic facts, had an excellent time, etc.
  2. Time feels much more valuable.  It’s no longer easy to find people to play sports with, and exercise seems more difficult to find time for.  I’m extremely out of shape compared to myself at the end of summer.  Some of this is me being lazy and some more is me being mentally weak;  I still make significant time for internet derping.  Also, time really does feel like it passes faster than it did when I was a child (a phenomenon many report).
  3. I’ve gotten far less stingy.  In particular, my meals get more and more expensive, on average.  Should money really have been worth that much more to me back then, relative to time and quality of life?   Perhaps I am somewhat over-valuing my time now?   It seems like this shouldn’t happen in general, but always does.  I wonder if something along the lines of Upstart will help mitigate this for high-value students in the future.
  4. I feel in no particular hurry to find a romantic partner, short or long term.  However, some uncertainty about my future values and the fact that many people my age seem to already be locking themselves into what will be long-term relationships makes that timeline feel somewhat shorter.
  5. I’ve become somewhat more selfish, or at least more uncertain about the balance between my altruistic and selfish values.  I still think all the time about how to make the world better, and I’m fairly committed to trying reasonably hard at this, but it seems like I will (continue to) spend a significant amount of time for selfish reasons (though perhaps not money).  I don’t care too much to change this, it seems, despite caring about “saving the world” type things.
  6. As I get older, I become somewhat less contrarian, for several reasons.  There are less things in the world I think are particularly dumb, and more things which I think are difficult to reason clearly about.  In social situations, there seems to be much more value in sticking to the norm than there was in the past.  I don’t regret much of the past though;  When young, being contrarian and weird has far fewer costs.  I also still have a huge affinity towards unusual ideas.
  7. Relatedly, I prefer to think of myself as a fox rather than a hedgehog, though realistically, it is not too true; I have mostly a very narrow range of skills and modes of thought.  I think I am moving slowly more towards the hedgehog direction, relative to the past.  On some issues, I am still staunchly hedgehoggy.

Pathery is NP-complete

Recently I’ve been playing Pathery, a game in which you place blocks to maximize the length of the shortest path in a grid (with some previously placed blocks already).

I had always been quite sure Pathery was NP-complete, but only a few days ago did I decide to really try to prove it, while out to lunch with Shaunak.  Together we came up with a simple proof.  It was much easier than I initially expected, and makes for a decent exercise, so stop reading if you don’t want this spoiled.

Read more…


I recently have been searching for jobs, and the process seems extremely annoying and inefficient.  Students have a separate, long interviewing process for each company, in which over half the time is spent on things that aren’t company-specific.  (And I suspect most interviews are terrible screens anyways).  Companies impose short deadlines in order to gain leverage, despite the fact that everyone graduates in seasons.  Negotiation has a huge amount of social friction.  Because things happen asynchronously, the resulting matching isn’t necessarily even any good.

Read more…

Singularity Summit 2012

I went to the Singularity Summit this year, primarily to meet interesting/smart people.  I also attended about half of the talks, and the videos are finally up.  Here are my thoughts on the ones I liked most:

  1. Jaan Tallin’s talk is super interesting, well-illustrated, and, considering the topic, audience-friendly.  Unfortunately, the video online doesn’t show all of his slides and animation, which were delightful.   The motivation for his talk is that we should be surprised that we appear to be on the verge of a singularity (supposing we believe that we are).  He proposes an anthropic explanation for this:  super-intelligences tend to simulate pre-singularity moments often (using a DFS-like algorithm), in order to see what other singularities look like (perhaps to find an intelligence to converse with).  I don’t find his argument that compelling, for a couple of reasons, but the talk is nevertheless fascinating and aesthetically pleasing.
  2. Robin Hanson’s talk is also extremely interesting.  He describes a particular era of a future with emulations – the very early stage, before there is self modification, super-organisms, etc. and things get much harder to analyze.  Trying to reason carefully in this world is an admirable goal and he does a great job, but I think the era he describes would be extremely brief (and not really exist as he describes it).  I also disagree with some aspects of his analysis – mainly the social/cultural things, like leisure (music, art) and relationships.
  3. Julia Galef on the rationality movement and Linda Avey on personalized genomics and medicine.  Pretty good talks about less interesting/far-out topics, but both things which I think are really important.  Julia gives a sort of hodge-podge of examples of how rationality is helpful (describing it sort of as breaking free from the chains of our genes), and briefly argues for CFAR’s cause of building a community around these ideas.  Very familiar stuff, if you’ve already thought about these sorts of things.  Linda has a Q&A, where she talks about her new company, which will hope to really leverage data about health and medicine, and a bunch of related topics.  Interesting to me throughout, since I didn’t know much about this sort of thing.

The effective altruism movement

I claim three things:

  1. Many people who profess some degree of altruism are not being very effective, despite their good intentions.
  2. Regardless of how ineffective their past decisions were, they can still make a huge difference, by joining the “effective altruism” movement and spreading the message.
  3. Even for those who are only slightly altruistic, it seems good to spend a small amount of time to help spread the word.

Read more…

Random links

Another round of links, because the internet generates interesting content much faster than I do: