For the December 29 issue of Nature, computer scientist Bernard Chazelle has penned a News & Views piece on a tantalizing idea known as the PCP theorem, which proposes that any mathematical proof can be immediately verified through randomization.
“To appreciate fully the significance of PCP,” writes Chazelle in his characteristically spirited style, “imagine you wake up one morning with your head full of a complete proof of the Riemann hypothesis. (This is arguably the greatest open problem in mathematics, and is a deep statement about the distribution of the prime numbers, the atoms of arithmetic.)” . . .
At last year’s annual meeting for the American Association for the Advancement of Science, Chazelle predicted that we will see an Einstein of algorithms in the near future. Ever since his AAAS talk, Chazelle’s ideas have been ricocheting through the cybersphere, mentioned most recently in HPC Wire.
In his reportedly very amusing AAAS talk, as well as in a piece he wrote for Math Horizons, Chazelle expressed bemusement over the recent precipitous decline in undergraduates majoring in computer science. Apparently, the decline has swiftly reversed itself. Computer science chair Larry Peterson reports that CS enrollment, at least at Princeton, is up by more than 20 percent.
You can find Chazelle’s original algorithm essay here. Or, if you are fluent in Greek, you might want to read this recent profile of him in Greece’s version of Time magazine.
