In Praise Of Chalk Talks
Chalking up a terrific talk on bit compression
Winsor McCay was a cartoonist and animator in the early part of the twentieth century, and authored the comic strip Little Nemo. He may not have invented the chalk talk—that could have been Frank Beard—but McCay made them popular with his vaudeville act, in which he drew faces and then progressively aged them. While these were over a hundred years ago, it appears from the history that blackboards were used in schools in India a thousand years ago.
Today I want to talk about content and delivery, about a great chalk talk and a great result.
What I liked so much is that Lance used a “chalkboard”—well he used our modern version of a chalkboard, a whiteboard. Most talks these days use PowerPoint or some LaTeX-based equivalent. Such talks can be informative and easy to follow, yet sometimes PowerPoint is not well suited to giving a proof. The slides do not hold enough state for us to easily follow the argument. There are tricks some try to use: dual projectors, a small image of the last slide on the current slide, and others. But “chalk” can always work well, especially in the hands of a master presenter like Lance.
I recall, eons ago when I was on the faculty at Berkeley, that on arriving there the math department asked me to give a special talk. It was an honor, and I was told the auditorium would be filled, so I was excited about giving it. In those days, before PowerPoint, we used slides on plastic and an overhead projector. These allowed the use of colors and overlays, plus other tricks that I often used. But the faculty member in charge of the invitation told me that there was a condition:
The talk must be a chalk talk.
I pushed back, but in the end I agreed to give a chalk talk. I did. When it was over he walked up to me, said “what a great talk” and then added “see, chalk is better.”
Lance’s result is about a kind of compression problem. I will just give an informal overview of the result and the proof. See his paper for details.
Imagine that Bob, our old friend, is confronted with the task of solving certain hard problems. He will be given a list
and he must select one of the problems and solve it. Each problem is encoded in bits, but there are of them. Note can be much larger than . This is what makes the task interesting.
Bob is in trouble. The problems ‘s are very hard—think -complete—and even with the choice of only solving one of them, he is in a “spot of bother.” What can he do?
Well there is an alien, who we will call Al, that is very bright. Al can solve any problem, I repeat any problem—decidable or not. Al is after all an Alien and he is very advanced. So the obvious idea is for Bob to send the full list of problems to Al and get the answer. So what is the difficulty? Why is there a talk, chalk or not?
There is a constraint. It is hard to communicate with Al, since he can only be reached by a special satellite phone that Bob has. So Bob can only ask Al a question that uses bits. The question can be anything, but it cannot be bits in size. This is the problem. Can Bob compress the problem he is given from bits to bits? This is the question. We insist, since Bob is not an alien, that the compression algorithm he uses must be computable in polynomial time. The theorem is:
Theorem: Bob cannot solve the problem unless
Put another way, Bob can succeed in his compression task provided some surprising result from complexity theory is true. Actually the “unless statement” can be showed to collapse the polynomial-time hierarchy so Bob is in real trouble. This last result is due to Chee Yap, who was one of my early Ph.D. students. A small world.
The proof of the theorem is pretty. The idea is to show via a counting argument that we only need Al for a polynomial number of bits. These bits form the advice bits used in the theorem, and so the theorem will follow. Why so few bits? The key is a simple counting argument
Recall that each problem is hard. So imagine there is a compression method. Then Bob can solve a particular by asking Al the compressed version of some
list of problems. His is in the list—note the key is the list is “padded” with other problems. If Al says “they all are false,” then of course Bob will know the answer to his problem. So given Bob must find a list that works. The key is that Bob does no care what other problems are in the list, but he does need that when is false they all are.
The counting argument shows that there must be an question that Bob can ask Al that will handle about half of all the lists. This follows by a simple counting argument. Then one amplifies it to handle all problems by the usual method of picking more such questions. The details are in the paper, and the theorem follows.
Do you like PowerPoint type talks or chalk talks?