# Turing lecture 2011

UPDATE: Video of the Turing Lecture now available here.

I am at STOC 2011, which is part of FCRC, the federation of CS conferences that meets jointly every five years.  This is far and away the biggest CS conference I have attended, and, even for STOC alone, the schedule is formidable.  The first talk was this morning at 8:30, and the (first-ever) poster session ends at 10:30 tonight.  And there are two parallel sessions.  In the past, I have mostly tried to attend every talk possible at a conference, and I am going to try something a bit different this time.  I plan to attend about half the available talks each day, and spend the rest of the time meeting people and writing blog entries about the talks I just attended.  Hopefully, I will learn more that way — and maybe people who didn’t attend will enjoy the “news reports.”

But, to begin at the beginning, the highlight of the entire federation of conferences took place last night, when Les Valiant, the 2010 Turing Award winner, gave the 2011 Turing Lecture to hundreds of computer scientists.  This talk was professionally videotaped, and I will try to remember to update this post when a link is available, but in the meantime, here are my impressions.

(Aside: Lance Fortnow and Richard Lipton have already blogged on Valiant’s winning the Turing Award.  See also this recent post by Lance that briefly mentions Valiant’s Turing Lecture.)

Valiant’s main thesis is that probabilistic machine learning is the way to address a fundamental open problem of evolutionary theory: How could organisms as complex as exist on Earth have developed after only 13.75 billion years?  If we model an extremely simple life form as a circuit, where each node in the circuit is a protein, we achieve an apparent contradiction from this seemingly quite reasonable model.  The contradiction: a complex life form alive today has perhaps 3 million genes.  There is no currently known subexponential way to build circuits for  complex functions, and yet life forms today are certainly able to solve complex functions.  Hence, it might reasonably require $2^{3,000,000}$ time steps to construct a complex life form, and, even if a “time step” is very small, the quantity still dominates the “mere” 13.75 billion-year age of the universe.

So Valiant’s point was that evolutionary theory is, at present, completely unable to give any rate of convergence arguments for Darwinian processes.  He took lengths to emphasize that he believes the evidence for evolution is overwhelming; he hopes to ramify biological understanding with theoretical computer science, not to point to the need for an intelligent designer.  Indeed, Valiant said the problem is the exact opposite of a “great mind” finding a “simple universe,” where, e.g., Newton or Galileo states a simple underlying concept such as the law of gravitation.  Instead, our tiny life form/circuit has no chance whatever of achieving understanding of a world that is prohibitively complex.  All it can hope to do is to get a little bit better than it was the day, or the generation, before.

The Lecture was high level, and intended for a broad audience.  Valiant gave a related talk in 2006 (slides, video),which contains more technical details.  That talk has a bug/feature that a biologist in the audience thought the approach was bogus and took the speaker to task for it, at length.  Valiant eventually just decided to stop talking.  There were no such problems at the Lecture last night, of course — though the videotapers kept putting Valiant’s image on the screen instead of the two technical slides!  So I will refer you to the slides from 2006 for technical details, instead of trying to reconstruct any Lecture specifics.

The gist: Valiant proposes that organisms learn about their environments by means of PAC learning (probably approximately correct learning, a notion Valiant defined in 1984).  PAC learning requires a “goal,” a function one is trying to learn, and it is often said that Darwinian evolution does not have a goal.  Valiant resolves this by proposing an “ideal function,” a function that has the answer to everything: given any set of circumstances as input, the ideal function outputs action X, the ideal action to take in the given situation.  Then under an evolutionary setting, circuits which better approximate the ideal function are favored to continue their line, while circuits with inferior approximations are likely to die off.  The math works out, if the ideal function and approximating functions are real-valued, and circuits can learn complex functions in subexponential amounts of time.  Hence, this provides a reasonable way to attack the problem of the rate of convergence of evolutionary processes.

As a final note, Chazelle, in his Natural Algorithms paper, provided the first-ever rates of convergence for longstanding control theory models of bird flocking, so it is allied to Valiant’s own approach.  Valiant went a step further than just saying that CS applied to other disciplines would be a good tool to obtain rates of convergence.  He noted that the parity function is not PAC-learnable, and said: People might object that the parity function does not appear in nature, but that is exactly the point; it does not appear in nature because it is not evolvable.