Fun with algorithms at Microsoft TechFest
It's a shame Microsoft only lets wizened old journalists into TechFest and not, say, packs of second graders. Because if there's anything that could show kids that math really is a ridiculous amount of fun, it would be a room full of people paid to find new ways to go about it.
All the truly significant tech companies have understood that somewhere at the heart of the firm, you have to make room for the guys who will never hand over an entirely shelf-ready product. That's true of most items found at TechFest, but it's a little more true of those working in theory -- and if you doubt me, ask the video crew charged with getting good footage of new search algorithms.
They did, on Tuesday, have the Gale-Berlekamp Light Bulb Game to photograph. If you remember the GB switching game from your own math or logic training, it involves an array of light bulbs, an adversary with access to all the switches, and a protagonist who needs to shut off as many bulbs as possible. The problem has a variety of applications in computing, particularly in communications complexity and circuit design, and Microsoft's made some headway on a linear time-approximation scheme for approximating GB-type problems.
Of course, much of math involves imagination -- dreaming up situations and seeing how they can be modeled and solved. Online ads placement, for instance, can be shaped as a set of game-theory questions; some parts are zero-sum games, some are collaborative games, and by thus decomposing and recomposing the problem, several researchers think they have a good way to maximize the effectiveness of online advertising.
Math matters greatly in the realm of security. One of the most promising developments on that front solves a decidedly non-mathematical problem: The difficulty of keeping one's private cryptography keys private. A system proposed on Tuesday allows for cryptographic implementations that can withstand partial disclosure of those keys, within limits. (No, you cannot just write your key down and stick it on the side of your monitor. Ever. There's still no mathematical cure for dumb.)
Perhaps the most impressive application of math to security on Tuesday came from members of the Bangalore team, which presented their research on an algorithm that can examine program node and infer specific information-flow security specs from it. The "Specification Inference for Security" would boost the capabilities of current static-analysis tools, which have to know what they're examining before they can parse it. The new algorithm does the static analysis, graphs the data flow and its constraints, converts the graph to a probability model, and looks at that to figure out where data may be endangered by the program's code.
Researchers Anindya Banerjee, Benjamin Livshits, Aditya V. Nori, and Sriram K. Rajamani have already published on their advance, which they call Merlin, in the upcoming ACM SIGPLAN 2009 Conference on Programming Language Design and Implementation (PLDI). Equally as impressive, they tried it out on 10 critical Microsoft business apps. According to an interview Nori gave to Microsoft's own Rob Knies, the tool eventually caught 335 vulnerabilities. If that's the success rate, your reporter's happy to go without those elusive algorithm photos.