CS Lunch talk Monday, September 12

Andrew Drucker ‘06 will discuss his summer research work with Professor Charles Kelemen:

"The Power of a Pebble in Computation"

In the extremely resource-bounded computational setting where all memory is read-only, the ability to drop and move a ‘pebble’ that serves as a placemarker seems like an invaluable tool. But in fact, the pebble can generally be eliminated without loss of computing power. This talk discusses old and new results about pebbles, and aims to give general audiences a viewpoint into theoretical CS.