Primes and Eratosthenes

Here's a short paper that talks about generating prime numbers. It's pretty interesting:
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf.

What Happened to the Quants in August 2007?

ahh the credit crunch. we've been through this sort of thing before, when black-shoals had a failing in its fundamental assumptions. found this paper via a buttonwood column in the economist, Heart of darkness, Oct 25th 2007, from The Economist print edition.

During the week of August 6, 2007, a number of quantitative long/short equity hedge funds experienced unprecedented losses. Based on TASS hedge-fund data and simulations of a specific long/short equity strategy, we hypothesize that the losses were initiated by the rapid unwind of one or more sizable quantitative equity market-neutral portfolios. Given the speed and price impact with which this occurred, it was likely the result of a forced liquidation by a multi-strategy fund or proprietary-trading desk, possibly due to a margin call or a risk reduction. These initial losses then put pressure on a broader set of long/short and long-only equity portfolios, causing further losses by triggering stop/loss and de-leveraging policies. A significant rebound of these strategies occurred on August 10th, which is also consistent with the unwind hypothesis. This dislocation was apparently caused by forces outside the long/short equity sector - in a completely unrelated set of markets and instruments - suggesting that systemic risk in the hedge-fund industry may have increased in recent years.

Khandani, Amir E and Lo, Andrew W., "What Happened to the Quants in August 2007?" (November 4, 2007). Available at SSRN.

How To Break Anonymity of the Netflix Prize Dataset

reminds me of the AOL search data hacks ...

We present a new class of statistical de-anonymization attacks against high-dimensional micro-data, such as individual preferences, recommendations, transaction records and so on. Our techniques are robust to perturbation in the data and tolerate some mistakes in the adversary's background knowledge.
We apply our de-anonymization methodology to the Netflix Prize dataset, which contains anonymous movie ratings of 500,000 subscribers of Netflix, the world's largest online movie rental service. We demonstrate that an adversary who knows only a little bit about an individual subscriber can easily identify this subscriber's record in the dataset. Using the Internet Movie Database as the source of background knowledge, we successfully identified the Netflix records of known users, uncovering their apparent political preferences and other potentially sensitive information.

Source: How To Break Anonymity of the Netflix Prize Dataset, Authors: Arvind Narayanan, Vitaly Shmatikov.
(Submitted on 18 Oct 2006 (v1), last revised 22 Nov 2007 (this version, v2))

Windows RNG

Writing a random number generator is a lot harder than most people think. A while ago some researchers dove through the linux source code and figured out how the linux random number generator worked. Yup, they had to reverse engineer it from the source! Anyway, they found a bunch of weaknesses. Well, guess what? Someone recently reversed the Windows RNG and found even more serious weaknesses.
http://eprint.iacr.org/2007/419.pdf

If you're into security, especially web security, you should probably know about this. It puts a big chink into SSL and other systems that rely on random numbers.

Mommy, Where do compilers come from?

A great slide deck on the process of bootstrapping a new language:

http://proglang.informatik.uni-freiburg.de/teaching/compilerbau/2004/T-diagrams.pdf

This one's a super quick read.

QMail retrospective

It's been ten years, what has QMail done for me lately? It certainly hasn't let me violate your security policies. DJB offers his analysis of ten years of QMail:
http://cr.yp.to/qmail/qmailsec-20071101.pdf
Good, preachy paper. DJB says why he thinks QMail was successful, why what other people are doing is a waste of time, and what we should be focussing on. Several priceless quotes from DJB and others are included.

The future of gaming?

This is a great slide deck on what goes into making a modern game with a roadmap for future success. It talks a bit about how languages and programming techniques can be used to reduce errors and exploit the parallelism of future machines:

http://www.cs.princeton.edu/~dpw/popl/06/Tim-POPL.ppt

Delimited continuations in Operating Systems

The stated purpose of this goal is to talk about something that might seem fairly obvious to most operating system writers: that operating systems are full of continuations. Ok, if you're an operating system geek you probably wouldn't call it this, you'd probably be thinking "setjmp" and "longjmp". Taking a look at this from a functional point of view with continuations is pretty interesting. Unfortunately this paper doesnt really talk about this subject as much as it promises! Instead they have a shallow introduction and then talk a little bit about their implementation of a tiny file server type operating system that uses continuations. Fortunately, this part is more interesting than it might seem. It shows how easily you can implement a transactional system using a pure language that provides familiar cursor/open/read/read type operations. Their whole implementation (available online) is 1000 lines of haskell.
The paper:
http://okmij.org/ftp/papers/context-OS.pdf
The site:
http://okmij.org/ftp/Computation/Continuations.html#context-OS

Total functional programming

Did you know you can write real programs in a language that isn't turing complete and has decidable properties? Turing complete languages have this pesky "halting problem" issue which is undecidable. Languages that aren't Turing complete aren't general enough to do anything useful. Or so you thought!

Read all about Total Functional Programming in this paper by Turner.

Using Z

OK, this one's a book, and not a paper...

The Z-notation is a formal notation for specifying programs. There's a free book online: Using Z

You might like this book even if you're not interested in writing specs for programs. Why? This book has one of the more readble and approachable introductions to predicate calculus, sets, functions and relations that I've seen.

Welcome back and a quick paper

It's been a long time since my last post. My apologies. I've been down the rabbit hole, reading all sorts of papers on functional programming, math, logic, type systems, proof systems, etc. Hopefully I'll get a chance to post about some of the more interesting ones here soon, but now is not the time. Instead I leave you with a single paper:

A tutorial on the expresiveness of fold by Graham Hutton.

This paper is a tutorial on the "fold" function (sometimes know as "reduce") which abstracts certain kinds of loops (or a certain kind of recursion).