## Wednesday, May 12, 2010

### What did he know and when did he know it?

Sometimes you learn a theorem in your academic career far later than you should have. Here are some examples.
1. I didn't know the classic upper bounds on the higher Ramsey Numbers until 2 months ago (note that I have been studying Ramsey Theory with a passionfor about 8 years). Upon hearing the theorem 8 years ago I came up with a proof of my own (which had TOWER bounds). I later forgot that I came up with it myself and thought it was the classic proof. I recently saw a reference that said it had double-exp bounds. This confused me so I looked it up and then realized that I never knew the classic proof! Now I do. And I have written up both my proof and the classic proof here. This is odd--- it is common to hear a proof and then later think you came up with it on your own. This was the opposite- I came up with a proof on my own and assumed I had heard it somewhere. I don't quite know what to make of this- I am happy that I came up with a new proof, but it gives worse bounds and is has no advantage whatsoever. (Both proofs are of about the same difficulty, though you can read them and see what you think.)
2. I know of two professors, one in Cryptography, and one in Parallelism, who did not know that every planar graph has a vertex of degree at most 5 until I mentioned it casually in a lecture. One said I missed the lecture on planarity in my graph theory class. While I believe this to be true I was surprised that he hadn't heard it somewhere else. Also, there is a point where you should stop thinking of knowledge in terms of courses you took. The other said Why should I care? My answer: it gives an easy proof that all planar graphs are 6-colorable, and it is the starting point for a fairly easy proof that all planar graphs are 5-colorable. He was not impressed.
3. A Complexity theorist I knew did not know that if you are operating mod a product of L primes, a number can have 2L square roots.
4. An Applied Math Professor I knew did not know that the reals were uncountable until I told him. He was a very practical person and didn't seem to care, calling it a mathematical trick. Oddly enough he used the term measure 0 sometimes.
5. Someone I knew who worked in Probabilistic Learning Theory did not know what variance is.
6. I knew a grad student in applied math who did not know that eπ i=-1.
7. There are several complexity theorists who do not know there is a c.e. set that is not Turing Equivalent to HALT and not decidable. When I tell them there is such they say Oh, just like Ladner's Theorem. This is true but sort-of backwards.
This raises the questions: (1) What should everyone know? (2) What does everyone know?

I would have thought that a planar graph having a vertex of degree at most 5 is in both categories, but perhaps I am wrong. I would have thought that knowing the reals are uncountable is in both categories, but here I am RIGHT.

So I ask you readers: name something you or someone you know found out far later in their academic life then is expected.

1. Our lab took on two junior-year electrical engineers as summer interns. It turned out that they had *never* measured an electrical voltage ... voltage for them existed only the output of SPICE simulations.

In a similar vein, it is now commonplace for astronomy grad students *NEVER* to schedule telescope time ... for their generation of astronomers, observational research is predominantly database mining.

Neither of these two cases reflects ignorance on the part of students; rather they reflect ongoing selective sweeps with respect to the profession-defining questions that Lance explored last week. e.g. "What is an electrical/quantum systems engineer?" ... "What is an astronomer?"

It will not surprise me if many responses to this post reflect selection sweeps, because these are becoming ubiquitous in modern academia.

A funny (and purely mathematical) example that comes to mind is "Grothendieck's Prime": the number 57. :)

2. Knowing too much is not necessarily good and can destroy your creativity. This is why mathematicians produce their best work only when they are young.

3. Several of these I just don't believe.

What does it mean that someone is "working in" statistical learning theory if they don't know what variance is? In particular, it means that they have never taken even an introductory college course on statistics or probability, nor are they familiar with tail bounds, and cannot have read very many papers.

I'm also skeptical of someone who you claim is an "applied mathematician" who does not know about Cantor's theorem. Do they have a PhD? In what field? It is impossible to take an undergraduate analysis class without learning this, and hard to imagine that without even a basic undergrad math background, you could go on to a PhD in math.

4. I didn't learn the maxflow-mincut theorem until at least five years after my PhD. I knew there were things called "flows" and "cuts"; I just didn't understand what they were.

Another embarrassing example: I didn't learn Boruvka's MST algorithm in any of my algorithms classes; for some reason, my algorithms textbooks and teachers only talked about Prim's and Kruskal's algorithms, even though Boruvka's is older, it's arguably simpler, it's more parallelizable, it runs in linear time on planar graphs, and it's the foundation of all more recent MST algorithms.

Oh, wait, that's (almost) everybody.

5. A related question is "what do some subfields of computer science not know that they should (and when will they learn it)?" I work in natural language processing. Although many people in NLP apply techniques from machine learning and formal language theory, I would say the average NLP researcher has surprising gaps in their knowledge about the ML fundamentals and basic complexity results--even those that are relevant to their work. In my own embarrassing case, I discovered Hammersley & Clifford Theorem was a year after I wrote a paper about conditional random fields. On the formal language side of things, parsing (our field's bread and butter!) and FSA-CFG intersection are basically the same algorithm, just a different interpretation of the results. The number of people in NLP who do not know this is probably extremely high.

6. In basic automata theory, I worked a while without noticing that, when an alphabet has 3 or more letters, one can produce words of arbitrary length without "squares", i.e. consecutive repeated sequence.

7. Bill's question seems to generate a lot of nonpositive responses, e.g. embarrassing stories of lack of knowledge.

How about a slightly more positive question: are there examples where someone KNOWING something from slightly outside their tiny area of expertise led to significant new results?

8. http://www.phdcomics.com/comics/archive.php?comicid=1056

:)

9. I didn't know a thing about truly interesting algorithms until I'd already spent a career programming solutions that worked fine for customers. That's because I never had to solve Google-sized problems, which are now the norm.

10. One just has to get used to the idea that there are a lot of things that we really all should know, but not enough time in which to learn them.
The list of things I think I should learn about grows depressingly quickly.

Heck, some of the things we think we know aren't even true: It's only finite planar graphs that need to have vertices of low degree.

11. I had a geography teacher in high school who had never heard of the Rosetta stone.

12. Found out 3 days ago that (for integer linear programs) the scary-sounding "Lagrangian relaxation" has the same value as the corresponding (real) linear program

13. A prof I talked with recently told me the story of an UK PhD candidate in a math department who, when defending, was asked, as a question of common knowledge, to show the shortest proof he knew on irrationality of sqrt(2). Turns out, he didn't know any. (This may be a bed time scary story for PhD candidates, though)

14. I wholeheartedly agree with Dan's comment and I am a little disappointed that this seems to have been taken by some as an opportunity to point out other peoples ignorance, rather than our own. I know that there is a vast amount I don't know, and even more that I don't know I don't know. If anything I can take consolation in the fact that as the amount I know I don't know grows, it is at least chipping away at that more dangerous category of things I don't know I don't know. Still, I would be quite annoyed if people started pointing out how ridiculous it is that I don't know X.

As regards the PhD example above, I think that is a rather unfair example. Having sat through a few vivas, it becomes pretty clear that people get caught out by the simple questions. I guess this is because their brain tells them it must be a trick, and they just lock up. It isn't necessarily dependent on whether they could or cannot answer the question without the pressure of the viva.

15. i really wonder what applied mathematics program you've been hanging around. maybe they should rename it to something else.

look, not everyone has had a real course in all of the following areas: (algebra, number theory, logic, complexity, analysis, algorithms, ...). everyone has a different idea about the important theorems there, and about which subsets should be easy for which fields.

it's super easy to find semi-contradictory sounding statements about these inclusion relations.

but really, it just sounds like bragging.

as a friend of mine used to ask, "are you bragging, or complaining?"

16. A former graduate student of (physicist) Julian Schwinger, whom I will call "B" told me this story ... in the 1950s "B" was working towards a math PhD ... took a required graduate course in algebra ... the concluding question of the final exam was "Give the eigenvectors, eigenvalues, and matrix inverse of this concrete 2x2 matrix".

"B" was the only student who calculated the correct answer ... the other students had grasped only the theorems, *not* the concrete calculation methods ... and after a serious talk with his math adviser ... "B" switched to the then-young discipline of field theory.

It worked for "B"! :)

17. I had an Arts teacher (named Karla) who didn't know who was Frida Kahlo, one of the most important XX century artist. She was a High School teacher at CESO (Centro de Ensino Setor Oeste), Brasilia, Brazil.

JoĂŁo Carlos

18. Please excuse my ignorance, but a graph with a central vertex of degree n (n > 5 say) connected to n vertices of degree 1 is planar but has degree greater than 5. Why is this not a counter example to your claim?

1. because you read the theorem incorrectly. reread it, slowly. then check your graph and see that it's still true of your graph. (that it contains a vertex of degree <=5).

a counterexample would be a planar graph all of whose vertices have degree 6 or higher.