Archive for July, 2011

In the last year, I have learned two excellent recipes that are amazing in terms of their deliciousness and simplicity. The internet being a great place to share great ideas, I hereby present you with: No-Knead Bread. Mix flour, salt, water, and yeast in the evening. Overnight the yeast will do the hard work. In […]

I recently read a paper by Dughmi, Roughgarden, and Yan, which is a novel cousin of the Lavi-Swamy technique I taught last term. The latter is a way of turning linear program-based approximation algorithms into truthful-in-expectation mechanisms that approximately optimize expected social welfare. The main result of D-R-Y is in the same family: a truthful-in-expectation […]

Last week I was at an excellent summer school organized by TU Berlin and held at a nearby cottage/hotel. One topic that came up in a couple of talks was new to me: parametric search. First I’ll describe the setting and the basic result, due to Megiddo from 1979. In an optimization problem, we are […]