ezyang’s blog

the arc of software bends towards understanding

February, 2012

Visualizing range trees

Range trees are a data structure which lets you efficiently query a set of points and figure out what points are in some bounding box. They do so by maintaining nested trees: the first level is sorted on the x-coordinate, the second level on the y-coordinate, and so forth. Unfortunately, due to their fractal nature, […]

  • February 26, 2012

Anatomy of “You could have invented…”

The You could have invented... article follows a particular scheme: Introduce an easy to understand problem, Attempt to solve the problem, but get stuck doing it the "obvious" way, Introduce an easy to understand insight, Methodically work out the rest of the details, arriving at the final result. Why does framing the problem this way […]

  • February 23, 2012

Transcript of “Inventing on Principle”

Here is a full transcript to Github of Bret Victor's "Inventing on Principle". It was transcribed by me, An Yu and Tal Benisty. Below is a copy of the transcript which I will endeavor to keep up to date with the Github copy. The original content was licensed under CC-BY. [[0:07]] So, unlike the previous […]

  • February 20, 2012

Travel: Spring 2012 Edition

For various reasons (mostly PhD-related) I will be traveling a bit over the next month. February 29 to March 2 in Princeton, NJ March 5 to March 7 in Pittsburgh, PA March 9 to March 12 in Palo Alto, CA Let me know if you're any of these areas and want to say hi!

  • February 18, 2012

How to build DRM you can trust

Abstract. Proof-carrying code can be used to implement a digital-rights management scheme, in the form of a proof-verifying CPU. We describe how this scheme would work and argue that DRM implemented this way is both desirable and superior to trusted (“treacherous”) computing schemes. This scheme permits users to retain control over their own machines, while […]

  • February 15, 2012