Reductions

We have all heard of the mathematician who poured out the water from the tea kettle, to reduce the problem of making tea starting from a filled kettle to one starting from an empty kettle that was already known to be solvable. Jokes aside, I really like reductions, they tie one problem within, by, to, over another.

There is a COLT 07 paper by Balcan, Bansal, Beygelzimer, Coppersmith, Langford, and Sorkin that shows how to reduce ranking (outputting the ranked order of entities) to classification (putting them into classes). Both problems are seen as machine learning problems, so one has to argue about generalization error, regret, AUC, or other suitable measures. This paper looks like a nice start (does one get useful algorithms? The algorithm seems to be to rank nodes by wins after running a tournament), the area sorely needs more work.

Dan Spielman, ever the thinker, after a day of talking about what are theoretical, fundamental problems in networking ("theory of networking" rather than "theory of computing"), suggested reductions. Could we take some fundamental networking problems such as convergence of asynchronous, distributed routing protocols and build some structure of relative hardness amongst them, via reductions?

I guess what I am saying is that reductions have already been used in theory of computing very nicely. time to use them in theory of machine learning, networking, games, whatever.