Archive for the ‘b.k.a.t.’ Category



Continuing on last week’s post, there were a couple of hands-on activities led by Joseph O’Rourke at the geometry minicourse that I attended. In one of them, you start by printing out the following sheet of paper (available at The red and green lines indicate mountain and valley folds and at this point your […]

Ravi Kannan gave a distinguished lecture today at Georgia Tech covering a wide swath of algorithms, randomness, and high-dimensional geometry. There was one particularly excellent slide that gave a very intuitive explanation for a result I have seen, but not fully understood, before. The result is in the field of streaming algorithms. Specifically, there is […]

Metroid. Introduced in 1986  by Gunpei Yokoi and Satoru Okada. Name is a portmanteau of metro and android (android is a combination of andr-, man, and –oid, likeness). Metroids are fictional jellyfish-like creatures with quadripartite nuclei. They are chased by the bounty hunter Samus. Killing them can be done with the help of the ice beam. Metroid. Introduced in […]

I saw a nice result sketched a few weeks ago, on the “online matching” problem. Below I try to re-explain the result, using some idiomatic (and as a bonus, inoffensive) terminology which I find makes it easier to remember what’s going on. Online Matching. There is a set of items, call them Lunches, which you […]

Last weekend I attended a conference in Budapest where I saw a nice trick in an unexpected place. (A longer report about the whole trip will appear on the CS Theory Blog.) Wikipedia calls it de Moivre’s martingale and the reason that I liked it is that it somehow gives me some intuition, that I formerly […]

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 […]

No, it’s not about the latest Wikileaks scandal. Thursday at EPFL, the last Bernoulli guest lecture of the discrete/computational geometry theme semester was given by Miklos Laczkovich, on geometrical tilings. (I posted about another of the guest lectures; the remaining 2 talks, by Gil Kalai and Micha Sharir, were excellent too.) Miklos’ talk was a survey […]