The two curses of dimensionality

The muse of geometry has cast two curses on our computers. We have all felt the one Bellman wrote about, but the other stands there like Cassandra awaiting our use of statistical methods. The curse of dimensionality made its print appearance in Richard Bellman’s 1957 book Dynamic programming. It was an outcry over the impossibilities of dealing with functions of many variables when a million bytes of memory seemed beyond imagination.…

Keep reading

General malware detectors are impossible

It is impossible to write a general purpose malware detector. Not hard, not difficult, impossible. The argument for the impossibility looks contrived, but it suggests that detection needs to be done probabilistically. The type of malware we often worry about is the type that alters the environment of the CPU. Programs that change data in the disk, that send information over the network, or that alter what is on our display.…

Keep reading

Given a wall, who wins?

Walls guard. Walls constrain. They defy us to break them. And so it has been since the dawn of agriculture. We see defensive walls protecting ancient cities from China through sub-Saharan Africa. Their widespread prevalence is a testment of their desirability. A wall around a city correlated well with the size of its merchant community, protecting the riches within from the ravages of medieval times while providing an overt display of the city’s wealth, power, and organizational skills.…

Keep reading

Markov's bound

I find it much easier to understand math from another person than from just reading it. One of my theories of why, is that the painful and tortuous way something gets understood is not the way it gets written up. In an attempt to expose that even simple things are not always that obvious, I captured the path I had taken while noodling over the Markov inequality by going over all the paper in my wastebasket.…

Keep reading

Grubbs' outliers

When collecting data for analysis strange things happen that make their way into the dataset. Sometimes those strange things are mistakes and we try to get rid of them, other times, they really are part of the data and we have to deal with them. Physicists trying to accurately measure the gravitational constant stumble on such strange things: the air conditioner in the lab next door cycles on-and-off creating small temperature variations, or they discover that the variation of the Earth’s rotation rate matters.…

Keep reading