


At the December 12 Lunch ‘n Learn, Chazelle began by confronting the four big ideas in computing: universality, duality, self-reference, and tractability. Universality owes its origin to Alan Turing, who explained first that it would be possible to create a computer that could load separate simple or complex programs and data. The result today is that we have iPods, Blackberries, desktop boxes and supercomputers that are essentially all the same in their architectural approach. Some are heavier, or more expensive, or more colorful or faster, but they are, thanks to Turing, the same. Turing took the idea of duality, the separating of the program from its data, from linguistics. Self-reference involves situations when the program and the data are equivalent, permitting replication of the program as in the replication of DNA from equivalent base pairs.
The modern era, suggests Chazelle, added the concept of tractability, whether tasks are difficult because they are hard, or because we simply don’t understand them. Intractable problems include map coloring, airline scheduling, protein folding, and calculating optimal tours for continuously traveling salesmen. Even with continuing advances in Moore’s Law, there appears to be insufficient processing available to solve such problems. Says Chazelle, the remarkable discovery is that all of these intractable problems are equivalent, variants of the same, in that if you can solve any one of them, though they look very different, you also solve all the others.
The most ingenious and powerful algorithms probably include Fast Fourier Transform (FFT) (useful in digital signal processing and solving partial differential equations), RSA (a key algorithm for cryptography, encryption, and e-commerce), and even Google’s PageRank (used to determine the relevance of web pages to specific search requests). Chazelle gave examples of algorithms that are vastly more amazing. Zero-Knowledge is an interactive dialogue in which one party can prove mathematically that a statement is true without revealing any knowledge. Zero-Knowledge is used in authentication systems in which one party wants to prove its identity to a second party without revealing anything about how it actually proves its identity.


An even more mind-boggling algorithm is PCP (Probabilistically checkable proof) that would permit us to determine the veracity of a proof simply by entering it into a specific format and then by checking a random number of its elements. If bugs exist, the formatting method will spread the error throughout the proof making it easier to detect.
In the future, algorithms will assist us with the deluge of many different kinds of data. Natural algorithms, essentially algorithms that come to us from nature, is an area of research that is most humbling, says Chazelle, because that is where we are most behind and because nature seems to adopt these algorithms so effortlessly. Nature folds proteins quickly and accurately, despite the fact that the algorithms governing such behavior appear to be intractable. Similarly, crowds move effortlessly through complex social situations, fish defend themselves from predators by shaping their bodies collectively to reflect light, and birds flock, swarm, and hunt in intricate and complex patterns. Chazelle notes that we want to build tools to understand these mechanisms, but classical mathematics won’t do and computer science, he insists, is not yet up to the challenge.
A podcast and the presentation are available.
