Friday, September 01, 2006

diagnosis of exclusion.

link to original piece.

The non-denial of the non-self

Aug 31st 2006
From The Economist print edition

How philosophy can help create secure databases

IN THE 1940s a philosopher called Carl Hempel showed that by manipulating the logical statement "all ravens are black", you could derive the equivalent "all non-black objects are non-ravens". Such topsy-turvy transformations might seem reason enough to keep philosophers locked up safely on university campuses, where they cannot do too much damage. However, a number of computer scientists, led by Fernando Esponda of Yale University, are taking Hempel's notion as the germ of an eminently practical scheme. They are applying such negative representations to the problem of protecting sensitive data. The idea is to create a negative database. Instead of containing the information of interest, such a database would contain everything except that information.

The concept of a negative database took shape a couple of years ago, while Dr Esponda was working at the University of New Mexico with Paul Helman, another computer scientist, and Stephanie Forrest, an expert on modelling the human immune system. The important qualification concerns that word "everything". In practice, that means everything in a particular set of things.

What interested Dr Esponda was how the immune system represents information. Here, "everything" is the set of possible biological molecules, notably proteins. The immune system is interesting, because it protects its owner from pathogens without needing to know what a pathogen will look like. Instead, it relies on a negative database to tell it what to destroy. It learns early on which biological molecules are "self", in the sense that they are routine parts of the body it is protecting. Whenever it meets one that is "not self" and thus likely to be part of a pathogen, it destroys it. In Hempel's terms, this can be expressed as "all non-good agents [pathogens] are non-self".

The analogy with a computer database is not perfect. The set of possible biomolecules is not infinite, but it is certainly huge, and probably indeterminable. The immune system does not care about this, because it has to recognise only what is not in its own database. Make one adjustment, though, and you have something that might work for computers. That adjustment is to define "everything" as a finite set, all of whose members can be known—for instance, all phrases containing a fixed maximum number of characters.

A database of names, addresses and Social Security numbers (a common form of identification in America) might require only 200 characters to contain all possible combinations. That would limit the total number of character combinations. A positive database containing all the data in question would be a small subset of those combinations. The negative counterpart of this database would be much larger and contain all possible names and addresses that were not in the positive database plus a lot of gibberish. But it would not be infinite. By looking at the negative database, it would be possible to deduce what was in the positive database it complemented.

That would not guarantee security against a search for the presence or absence of a particular name and address. Indeed, the whole point is that such searches should be possible. But it would prevent fishing expeditions by making it impossible, for example, to look for the Social Security numbers of all the people living on one street.

Dr Esponda sees great potential for using negative databases when there is a need to look at the intersection of many sets of data owned by different parties. Two or more banks, for example, might wish to work out which transactions they have in common without revealing the whole contents of their databases. Using negative databases to do this would, according to Dr Esponda, provide a robust back-up to traditional cryptography, which relies on codes that can be broken.

An interesting extension of the idea might be to use negative surveys to collect sensitive information privately. Dr Esponda gives the example of a negative survey in which respondents are asked to tick the box of one sexually transmitted disease they do not have. He reckons that this would be sufficient to estimate the population frequency of each disease, without having to ask people whether they actually suffer from such diseases—which is intrusive and also invites lying. As he puts it: "In Hindu philosophy, to find out who you are, you ask what are you not. Then you are left with what you are."

This is not your childhood origami.

link to original piece.

The Extreme Sport of Origami
A physicist's computer program speeds the creation of stupefyingly complex paper sculptures.
By Jennifer Kahn
DISCOVER Vol. 27 No. 07 | July 2006

Robert Lang was still working at his day job as a physicist in Silicon Valley when the bug wars broke out. Back in the early 1990s, the skirmishes were mostly local, the contestants mostly Japanese. "The first year, someone had a six-legged bug," he recalls. "The next year, it was a six-legged bug with antennae." A few years later, Lang joined the fray. For a formal bug-design challenge, held in 2004 on a muggy June in Manhattan, Lang and two competitors agreed to test themselves by creating a Eupatorus beetle. Eupatorus beetles are not simple insects. Sometimes called rhinoceros beetles, they have five horns of mixed length on their heads, tiny, vertical spurs at the joints of their six knees, and delicate, complicated toes. The contestants had to reproduce all these features on the Eupatorus, along with the rest of the beetle, out of a single uncut rectangle of paper. For the serious student of origami, making a Eupatorus is an extreme challenge.

In the dojo of the origami purist, there are only two rules: The folder may use just one sheet of square paper, and the paper cannot be cut or torn in any way. Following these rules to make a figure like a peace crane, with four basic features—a head, a tail, and two wings—is relatively easy, and origamists traditionally proceeded by trial and error, unfolding and refolding a piece of paper until it started to resemble, say, a swan. For hundreds of years, origami's most complex patterns topped out at 20 steps.

These days patterns requiring more than 100 steps are common. Some of that competitive acceleration is due to Lang, who transformed the art by writing a computer program that can generate the blueprint for ultracomplex origami sculptures. Even with digital assistance, figuring out the sequence of folds that will create a beetle and all its ornaments is a mathematical problem of staggering complexity. Still, the reigning champion of intricate origami is a 23-year-old Japanese savant named Satoshi Kamiya. Unaided by software, he recently produced what is considered the pinnacle of the field, an eight-inch-tall Eastern dragon with eyes, teeth, a curly tongue, sinuous whiskers, a barbed tail, and a thousand overlapping scales. The folding alone took 40 hours, spread out over several months.

"It's like an extreme sport," says Tom Hull, a mathematician at Merrimack College in North Andover, Massachusetts, and longtime origami enthusiast. The escalation in difficulty has grown so severe that OrigamiUSA has been forced to add a new difficulty rating to the four (simple, low intermediate, high intermediate, and complex) it has traditionally used. "People showing up to the complex sessions were getting blown to smithereens," Hull explains. "So now there's a new category: supercomplex."

At its core, origami consists of just two folds, mountain and valley. A mountain fold is what you get if you crease a piece of paper so that it stands up like a pup tent. A valley fold is the same thing turned upside down. Valley folding each corner of a square so that they meet in the center creates something that looks a bit like a cheese blintz and is therefore known as a blintz fold. Beyond these two basic folds, the grammar of origami proliferates rapidly. It's possible to blintz a petal fold, or double blintz it. Likewise, combining a series of squash and petal folds yields a frog base—one of the four traditional bases (called kite, fish, bird, and frog) from which many traditional origami animals are fashioned.

"All the parts of a base are linked together and can't be altered without affecting the rest of the paper, so that's the part you have to calculate just right," Lang says. A base with four flaps is relatively easy to make. Each flap is formed from one of the corners of the square. Making a base with 17 flaps of the right size and in the right places—what you'd need to create Lang's flying rhinoceros beetle—is exponentially more difficult. "Figuring out how to make good legs was all people did for years," Tom Hull says. "Doing a six-legged beetle was a big, big deal."

Lang resisted the challenge for a while. He spent most of the past two decades working as a laser physicist—first at Caltech, then later for private firms in Silicon Valley—and devoted his off-hours to origami. By 2002, his interest in origami won out. He quit his job and began folding paper for a living.

Since then, he has created everything from a ruby-throated hummingbird to a full-scale human (commissioned for a German trade show). The jobs are sometimes banal—there's a lot of demand for cardboard fast-food containers that change shape—but every now and then Lang gets tapped for a more challenging project. He has been asked to simulate the folds of a car's air bag when packed into a steering column and to design a telescope lens that could be shot into space packed into a nine-foot cylinder and then unfurled to the size of a football field. He also recently consulted on the development of an origami-inspired medical implant, which he can't talk about other than to say that it was "big, permanent, and what keeps the person alive." Origami also turns out to be useful for biological problems, such as determining how proteins fold in the body.

Over the past 15 years, Lang has been perfecting a program he wrote called TreeMaker, which can render a stick-figure sketch into a crease pattern—the web of lines that would be left if a finished piece of origami were unfolded and then smoothed. The software converts the sketch into a set of equations that calculate how the appendages of a complex animal form, like a deer, should be distributed on the paper in a way that ensures they will neatly emerge during folding without leaving excess paper or creating areas so wadded up that they can't be folded.

Riffling through some papers on his desk, Lang pulls out the crease pattern that TreeMaker generated for a white-tailed deer. More than 200 equations factored into the algorithm. The resulting crease pattern—a network of lines running over a collage of circles joined by crenellated segments that Lang calls rivers—resembles a deer about as much as a cotton bush looks like a pair of jeans.

"Those are the ears," he says, indicating two small circles in opposite corners of the page. He taps some wavy lines that look like linked Japanese footbridges. "And that's the neck." He sees the uncomprehending look on my face and seems slightly embarrassed. "You just have to take it on faith, that when you collapse it down the right way, you'll get a leg."

Among origamists, TreeMaker is a revolutionary tool that saves hours formerly spent on folding and refolding just to get a simple animal's proportions right. Lang, however, is quick to point out that the program does not tell the artist what steps to take to get from the crease pattern to the final shape. An origamist is left to puzzle out the folding sequence, deciding upon the correct order and direction, out of literally millions of possible combinations, in which to make each crease.

Calculating this, as mathematicians like to say when facing a daunting challenge, is not trivial. Fold a square piece of paper diagonally, then fold it in half, and the result will be a small isosceles triangle. Switch the order of those folds—in half first, then diagonally—and you end up with a squashed pentagon.

The more folds a pattern has, the harder the problem of finding a folding sequence becomes. For one of his TreeMaker-guided designs—a life-size, anatomically correct Maine lobster—Lang was able to generate the crease pattern on the computer in just a few hours. Figuring out how to fold the 120-step pattern on a sheet of paper about 20 inches square took him almost two years.

"The mind-set to do advanced design is fragile," Lang says soberly. "You have to hold all these complex surfaces in your mind and figure out how they interact. If you're pushing the edge of the envelope on something like this, you need total concentration. Sometimes you'll have 5, 10, 20 creases, and you have to make them all happen at once. You need to develop an intuition about it."

To perfect their folding technique, Lang notes, rookies must also attend to details, like not creasing folds too sharply. "Do that and your piece will end up looking tatty. Plus, if there's a point where a lot of those creases come together, the paper can burst. It just puts too much strain on the fibers."

Lang gets many of the raw materials for his designs from Michael LaFosse, a master papermaker in Massachusetts. Among the exotic varieties are hairy paper, shiny paper, and paper so ethereal it seems to be made of fireplace ash. Nepalese lokta, a handmade fiber paper studded with tiny, grassy knots, is one of Lang's favorites—although he is also partial to abaca, a veiny material made from banana fiber. He almost always uses papers made from plant fibers other than wood pulp because they take a crease better and are less likely to rip under stress.

Origamists also toy with color, using papers that are irregularly mottled or that are one color on the front and another on the back. This aesthetic detail adds another layer of complexity to the crease pattern, which must then be designed so that the final animal—a bumblebee, perhaps, or a zebra—ends up with the right colors in the right places. In one famous example, origamist Neal Elias created a dancing couple from a single sheet of paper, folded so that the man was dressed entirely in black, the woman entirely in white. Lang recently made a lion out of fiber paper and folded it so that the paper's four original edges all ended up in the lion's mane. The edges were frayed, which made the mane authentically shaggy.

Although Lang is one of the world's top origami folders, he admits that his pole position is anything but secure. "The current generation is really remarkable," he says cheerfully. "Satoshi Kamiya, for instance, is just brilliant. He started as a child prodigy and came to the attention of the world origami community—the world community—by the time he was 15."

Unlike most elite origamists, who are often engineers or mathematicians, Kamiya is simply a genius. In Japan, where elementary origami is a popular pastime, Kamiya started folding with his mother when he was 2 years old. Early on, he showed a preternatural talent for visualizing complex geometric shapes. By age 10, he was designing his own sculptures. Last year he published a book, Works of Satoshi Kamiya: 1995–2003, which includes all his original designs. And he recently began making his own paper, which he engineered to be exceptionally thin and strong. "It was the only way he could make something so complicated," Tom Hull says. "The designs he's coming up with exceed the properties of ordinary paper."

For four years running, Kamiya has been crowned Origami TV Champion in a contest hosted by a Japanese game show. Some competitive events are almost maniacal in their intricacy. One year, he had to fold a fish underwater using waterproof paper. The next year, he was asked to fold animals that he first had to catch: a dog, plucked from a pen of 20 different breeds, and a fish scooped from a tank. The judges were fishermen and dog breeders; the winner folded the most animals whose breed was unmistakable.

Origami aficionados agree that Kamiya's most extraordinary sculpture is a dragon he created in 2004, at age 20. Coiled and rearing, the dragon has the lithe energy of a living snake, with overlapping scales, thornlike teeth, and tiny, grasping, clawed hands. Asked how he manages to create something so complicated without the help of a computer, Kamiya pauses to consider. "I see it finished," he says finally. "And then"—he stares off, as though visualizing the imaginary object—"I unfold it. In my mind. One piece at a time."

Lang and Kamiya meet often at exhibitions, but their methods remain distinct. Lang continues to tinker with TreeMaker, sticking with the computer-aided approach. Last year he devised a tricky algorithm to solve whether folds in a TreeMaker crease pattern were mountain or valley. Kamiya, too, continues to experiment, but he has no interest in learning to use TreeMaker. In halting English he says: "Right now, human way is better."

Meanwhile, the bug wars go on. At OrigamiUSA's annual convention in New York City this summer, Lang goes up against half a dozen other folders, including Kamiya, in a bid to make a sailing ship. Lang is mulling over a couple of approaches, but "frankly," he says, laughing, "I'd be putting my money on Satoshi Kamiya."