Professor of Computer Science at UC Irvine, researching graph algorithms and computational geometry. Wikipedian. Amateur photographer. Father of two.
0xDE's Latest Posts
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 […]
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.
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 […]
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 […]
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 […]
Log in to leave a comment