April 14, 2014

6:50 AM | From when even the cars had moustaches
Every year about this time, my campus holds a spring celebration, with all the student organizations setting up pavilions in the park to sell food and advertise for new members, with the creative anachronists bashing each other with padded swords, and with a car show. Why a car show? I don't know, but I always enjoy seeing the variety of shapes and colors compared to today's mostly-the-same boxes. My favorite this year was a 1950 Chevy Fleetline, found rusting in a swamp in Tenessee; after a […]

April 13, 2014

5:07 AM | Congratulations to Tetsuo Asano
When I last saw Tetsuo Asano, he was giving a research talk at WADS, and openly worrying that it might be his last one. We all thought it was because of mandatory retirement (still legal in Japan). But, it turns out, no. Instead, he's the new president of JAIST. Congratulations, Tetsuo!I'll probably miss SoCG, in Kyoto this year, but for those who will be going, there will be an associated workshop in honor of Asano's 65th birthday.

April 12, 2014

12:42 AM | Using complete binary trees to prove the power of two choices
The power of two choices in load balancing is well known: If one throws n balls independently at a similar number of bins (as in hash chaining), some bin will typically have Θ(log n/log log n) balls in it, but if one draws two random bins for each ball, and places the ball greedily into the less-full of these two bins, the maximum load will be much smaller, Θ(log log n). And if one clairvoyantly chooses which of the two bins to place each ball into (or uses […]

April 05, 2014

10:18 PM | Upgrade to Mavericks
I had been running Snow Leopard (OS X 10.6) on my Macs, because I wasn't convinced that later versions were much of an improvement in usability. But Apple has apparently stopped providing security updates for a version as old as mine, so this week I updated to Mavericks. So far I've encountered only minor glitches: the update lost a couple of configuration settings (the monitor arrangement for my two-screen desktop and the preferred browser on my laptop), I had to reinstall git and update […]
7:18 AM | Graphs with many cycles and doubled cycle minors
This one isn't my problem – it came from MathOverflow – but it's frustrating me that I haven't been able to solve it, so I hope by reposting it here I can get some more attention to it and maybe even a solution.The question is: let Fk be the family of graphs having no minor in the form of a cycle with doubled edges, of length k. Do the graphs in this family have a polynomial number of cycles (with the exponent of the polynomial depending on k, ideally linear in k)?Here are some […]

March 29, 2014

6:07 AM | Greetings from Barbados
I'm back now, but this beach house in Barbados was my home for the last week, as I attended the 29th Bellairs Winter Workshop on Computational Geometry (my first time there).The format of the workshop is very much aimed at making new research, not just sharing what the participants have done elsewhere (as many other workshops and conferences do). We met as a group twice each day for three-hour group sessions, one in the morning and another in the evening, with afternoons as free time. The […]

March 20, 2014

5:10 AM | Cages
The cages are a class of graphs that I think deserve to be more widely known, because they have a lot of interesting properties that make them useful as counterexamples in graph algorithms and graph theory. They're hard to construct and we don't have a lot of explicit descriptions of them, but that's not so important when you're using one as a counterexample. First, what is a cage? The cages are parameterized by two numbers, r and g. An (r,g)-cage is a graph that: is r-regular: each vertex is […]
Editor's Pick
7 Results