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.

The talk was just given at our ARC day by Lance Fortnow, and the result is his with Rahul Santhanam. The paper is titled Infeasibility of Instance Compression and Succinct PCPs for NP.

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.”

## The Result

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

$\displaystyle P_{1},\dots,P_{M}$

and he must select one of the problems ${P_{i}}$ and solve it. Each problem is encoded in ${n}$ bits, but there are ${M}$ of them. Note ${M}$ can be much larger than ${n}$. This is what makes the task interesting.

Bob is in trouble. The problems ${P_{j}}$‘s are very hard—think ${\mathsf{NP}}$-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 ${M}$ 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 ${n^{2}}$ bits. The question can be anything, but it cannot be ${Mn}$ bits in size. This is the problem. Can Bob compress the problem he is given from ${Mn}$ bits to ${n^{2}}$ 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

$\displaystyle \mathsf{NP} \subseteq \mathsf{co}\text{-}\mathsf{NP}/\text{poly}.$

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

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 ${P_{j}}$ is hard. So imagine there is a compression method. Then Bob can solve a particular ${P_{j}}$ by asking Al the compressed version of some

$\displaystyle P_{1},\dots,P_{M}$

list of problems. His ${P_{j}}$ is in the list—note the key is the list is “padded” with ${M-1}$ other problems. If Al says “they all are false,” then of course Bob will know the answer to his problem. So given ${P_{j}}$ 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 ${P_{j}}$ 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.

## Open Problems

Do you like PowerPoint type talks or chalk talks?

1. November 7, 2013 1:44 pm

For high level understanding ppt, for more insight chalk.

November 7, 2013 3:36 pm

A long time ago, teaching at Penn State, I could joke that the professors were liable to get White Lung Disease. Now that falls flat, with PPT, white boards, and too few children of coal miners.

Chalk slows you down, and PPT forces out details. Both effects are important for a one-shot concept-level presentation. For classroom lecture notes, I use plain dumb HTML, leaving in the details.

Still in awe of Roger Penrose’s handwritten multi-color transparencies.

November 7, 2013 4:17 pm

The phrasing of the American novelist Wallace Stegner, as interpreted by the essayist Wendell Berry — in minutes 16:00 to 18:15 of Berry’s 2012 Jefferson Lecture — suggests the following:

Proposition  PowerPoint talks are suited to “academic boomers” and chalk-talks are suited to “academic stickers.”

What are “academic boomers” and “academic stickers”? Bill Thurston’s celebrated article On proof and progress in mathematics (arXiv:math/9404236) amounts to a “sticker’s credo” for mathematicians.

As we contemplate a 21st century world that (almost certainly) will soon have ten billion people in it, and that (very hopefully) will provide satisfying family-supporting work for those ten billions, and as we further imagine the various crucial roles of STEM work in that hot, crowded, yet exhilarating world, we are led to reflect that the disparate strengths of Berry’s lecture and Thurston’s essay are (as they seem to me) even stronger when these two “chalk talks” are considered in combination, than when they are considered separately.

4. November 8, 2013 4:18 am

I don’t get it. Why can’t Bob pick some problem $P_k$ which is of size $n<n^2$ bits to Al and get it solved?

November 8, 2013 9:58 am

The way this is phrased leaves me puzzled as well. In the paper, the problems are boolean formulas, and the goal is to decide if at least one is satisfied. I don’t see how this is related to the problem of solving one NP-complete problem out of a list.

November 8, 2013 5:11 am

You write: “and he must select one of the problems {P_{i}} and solve it”.
But this should be: “and he must decide whether at least one of the problems {P_{i}} has answer YES”

November 8, 2013 9:38 am

qqq*

That is right that Al solves the OR problem. But Bob uses the OR problem to solve his own single problem. I am sorry if I was unclear. See the paper for the details

6. November 11, 2013 10:57 am

PvNP is old news. Whats the next one?

I asked the FBI to allow me to give the solution for PvNP to the Middle East because I have Arab/Jewish background and wanted to help them out a little bit concerning their stumbling block of having unleashed the concept of zero into the world, and they stated that if i do it they will claim me to be a traitor to America. So what good is a solution if you can only publish it after you die, which is why people need not look for things that cause more pain than pleasure.

P v NP was actually very simple problem to solve. I intuitively felt the solution once i transitioned from Sequential Math II to Sequential Math III and realized the flaw in trigonometry (which for me was exacerdated by a general misunderstanding in all mathematics that is being taught in the early stages of every childs transition from pure arithmatic to number theory). The solution is probably too simple which is why i am asontnished that the public never really saw it for what it was (a mathematical dyslexia in not observing the super-symetry between masculine and feminine computational schemes). Why is it that only governments have the solution while everyone else in the mainstream is blind as a bat

7. November 11, 2013 11:14 am

The solution to PvNP is also the solution to arithmatic v number theory, geometry v trigonomentry, general relativity v quantum mechanics, mind v matter, and a solution to many dilemas in other fields of science ranging from biology to psychology to sociology. Moral of the story? How you compute is just as important as what you compute. A flaw in either dimension causes chaos and disequilibrium in our super-symetrical multi-dimensional universe.

8. November 12, 2013 1:30 am

Chalk talk any day over a canned talk (in my case LaTex, specifically Beamer, not .ppt). With carefully written out panels on the board, the last three or four “slides” are still available for the audience, if they need them, to follow what you are saying, e.g. a proof.

If you want to kid yourself that you’ve “covered” lots of material, then .ppt — but if you want to educate the audience (not to mention yourself), then chalk talk or its equivalent any day!

A propos Don Heller’s comment: I too used to joke about “white lung disease” but that joke fell flat even thirty years ago! Nowadays I joke about getting high on the solvent that is in the white board cleaner. That joke falls equally flat. Guess I was never meant to be a stand-up comedian! 😦

9. November 12, 2013 2:21 am

Both. (I am talking about the Open Problem.) Simultaneously. And, actually, something more.

On the rare occasions that Indians have allowed me to teach (I mean in the recent past of the last decade or so), I have found that the best strategy is:

(i) to use slides on a side-screen (actually the plain wall besides the white-/black-board works great!)

(ii) and to keep the white-/black-board at the center, and extensively use it to explain the points as they systematically appear on the slides.

It’s the same old bones-and-flesh story, really speaking. Both are necessary.

Even if you don’t use the slides for a lecture, preparing them is still advisable, because a lot of forethought thereby has to go into structuring your presentation (including some thought about the amount of time to be allocated to each sub-unit of a lecture). Why, if you prepare the slides, even if you don’t use them, you would find that your management of the black-board space has improved a great deal!

I know quite a few professors who seem to take the ability to deliver a lecture without referring to any notes or slides, as the standard by which to judge the lecturer’s own mastery of the subject matter. Quite fallacious, but somehow, at least in India (where there always is a great emphasis on memorization rather than on understanding) this opinion persists widely. (And, the lecturer’s own mastery, even if necessary, is not at all sufficient to generate a great lecture, anyway. Newton in Cambridge would teach mostly to empty benches.)

The flow of a spontaneously delivered lecture is fine, as far as it goes. But far too many professors have this tendency to take things (students, actually!) for granted. If you don’t prepare slides, it’s easy—far too easy, in fact—to do that.

I have known the “free-flowing” type of professors who would habitually dwell on the initial and actually simpler part of a lecture for far too long (e.g., spend time in drawing the reference diagrams (think FBD of mechanics) or in discussing the various simple parts of a simple definition, etc.), and then realizing that “portion is to be finished,” hurriedly wind up the really important points in the last five minutes or so. For example, I have seen some idiots spend up to 45 minutes explaining the simplest points such as, say, the household plumbing as an analogy for the electric circuits, or the movement of a worm as an analogy for the edge dislocation motion, and then wind up in the remaining 15 minutes the really important topics like the Thevenin/Norton network theorem (EE) or mechanisms of dislocation growth (materials science).

Maths types are the worst as far as the so highly prized “flow” (and showing one’s genius by solving problems on the fly on the black-board without ever referring to notes) goes. Well, if you are going to prize your own genius in that manner, some other things *are* going to get sacrificed; they do! Ask yourself if your UG ODE/PDE teacher had appropriately emphasized the practically important points such as the well posed-ness of the DEs, or, for that matter, even the order of a DE and the number of auxiliary (boundary and/or initial) conditions that must be specified—whether you can have both the flux and the field condition at the same point or not, and why. I have known people who got these points only while taking post-graduate engineering courses like CFD or FEM, but not from the UG mathematics professors proper. The latter were busy being geniuses (i.e. calculating, without referring to notes or slides).

All such folks must face the arrogance of their idiocy if (to them) the highly constraining rule that slides must be prepared in advance for every lecture, is made compulsory.

You can never make anything fool-proof, of course. For every “free-flowing” guy of the above kind, there always is that despicable “nerdy” type… You know, one who meekly slides into his class with his slides/notes, hangs in nervously there for the duration of the lecture, puts up the slides and reads them aloud (if you are lucky, that is—I have suffered through some specimens who would merely mumble while vaguely looking somewhere in the direction of the slides), “solves” the problems already solved in the prescribed text-book, and then after a while, leaves the class with somewhat less meekness: carrying on his face some apparent sense of some satisfaction—of what kind, he alone knows. *These* types could certainly do well with the advise to do some chalk-work.

With slides, diagrams can be far more neat; students can copy definitions/points at their own convenience during the lecture and you don’t have to wait for every one in the class to finish taking down the material before proceeding further because they know that hand-outs would be available anyway (because these are very easy to generate); and the best part: you don’t have to worry too much about your hand-writing.

In between PowerPoint and LaTeX, I personally like Beamer because: (i) its template makes me feel guilty any time I exceed three main points for an hour-long lecture (though I often do!), and (ii) I always have the assurance that the fonts won’t accidentally change, or that the diagrams wouldn’t begin floating with those dashed rectangles right in the middle of a lecture. And, it is free. For a mostly jobless guy like me, that helps.

Finally, one word about “more.” Apart from chalkwork and slideshows, there are many other modalities. Even simplest physical experimentation is often very useful (e.g., tearing a paper in a class on fracture mechanics, or explaining graph algorithms using knotted ropes, say as hung down from this knot vs that knot, etc). Physical experimentation also kills the monotony and the boredom.

In my class, I also try to use simulation as much as possible. By simulation/animation, I do not mean the irritating things like those alphabets coming dancing down on a PowerPoint slide as if some reverse kind of a virus had hit the computer. I mean real simulations. For instance, in teaching solid mechanics, FEM simulation of stress fields is greatly useful. I gained some of the most valuable insights into classical EM only by watching animations, e.g., noticing the fact that changing an electric current changes the magnetic field *everywhere* simultaneously. In CS, you can spend one whole hour throwing slides on the screen or doing chalkwork or even stepping through code to explain how, e.g., the quicksort differs from the bubble sort, but a simple graphical visualization/animation showing the sorting process in action, delievers a certain key point within 5 minutes flat; it also concretizes the understanding in a way that would be imposible to achieve using any other means.

My two/three cents.

–Ajit
[E&OE]

10. November 12, 2013 5:16 am

In the mathematics department at Queen Mary we have very nice blackboards (“chalkboards” across the pond, I guess) in both the lecture theatre and seminar room. But the lecture theatre is not big enough for our largest classes so we have to use other rooms across the university which, if you are lucky, have whiteboards, and if not, just projector and screen (but the projector may be connected to a document camera as well as a computer).
I much prefer chalk talks (or, if necessary, whiteboard talks) when lecturing to students. This for many reasons; the most important is that they slow me down to their speed. Indeed, any talk where I am not pushed for time I prefer to give on the board. But often now, conference organisers allocate 15 or 20 minutes. Then I cannot even attempt to explain; all I can do is to give a trailer, and try to catch people’s interest. For this, a beamer talk is the only option.
Some years ago, the students nominated me for a teaching prize. I had to submit a teaching portfolio explaining my innovations in teaching. I almost didn’t bother, but finally I said that my main innovation was writing everything on the board, with a piece of chalk if possible. Much to my amazement, they gave me the prize. The sequel was that the vice-principal in charge of teaching (who favours innovation) presided at the graduation ceremony, and was quite shocked when I was presented with the prize certificate and the graduating maths students stood up and gave me a Mexican wave. What a moment!

11. November 28, 2013 2:02 am

PowerPoint talks are good for one thing only – insomnia

• November 29, 2013 11:48 pm

Not if the lights are on! 😦