Clyde Kruskal talks about his Father Martin on Martin's 100th birthday

Martin Kruskal was born Sept 28, 1925 and passed away on Dec 26, 2006, at the age of 81 (we did two posts for his memorial, here  and here). Today, Sept 28, 2025, is his 100th birthday. His son Clyde Kruskal wrote today's blog post as a tribute to his father.

We note that Clyde did a blog for his Uncle Bill's 100th Birthday, here, and plans on doing one for his Uncle Joe in two years. 

-----------------------------------------------------------------------------------------

My father, Martin Kruskal, was a mathematician and physicist, best known for his early work in plasma physics, the discovery (independently of George Szerekes) of Kruskal-Szerekes coordinates, the modern discovery with Norman Zabusky of solitons, and the discovery with Clifford Gardner, John Greene, and Robert Miura of the inverse scattering transform.  He had an incredible willingness to tackle interesting, seemingly small problems\(-\)some of which later turned out to be highly influential.  Here, in chronological order, is a list of some of his more esoteric and/or less well-known contributions, not necessarily research contributions (besides me).


1. Random Mappings

Renowned mathematicians Nicholas Metropolis and Stanislaw Ulam (inventors of the Monte Carlo method) posed the problem of determining the expected number of components in a random mapping from \(N\)  to \(N\). Framing this as a random graph problem: Construct a graph on \(N\) vertices by choosing, for each vertex \(i\) (from 1 to \(N\)), a random vertex \(j\) (also from \(1\) and \(N\)), and create the undirected edge \((i,j)\). If \(i=j\), no edge is created (or equivalently, a self-loop is created).  The question is: What is the expected number of connected components in such a graph?  In 1954, in his first paper after graduate school, he showed that this value is asymptotically \((1/2)(\ln(2N) + C) + o(1)\), where \(C=0.5772\ldots\) is Euler's constant. For the paper see here.

2. Computer Chess

My father was a strong chess player and, in 1956, arguably became the first person to play a game of chess against a computer.  When I learned about this in junior high school, I figured that this must be his most significant achievement.  Because the MANIAC 1 computer was slow and had little memory, the game was played on a 6×6 chessboard without bishops and simplified rules.  My father gave the computer queen odds. Spoiler alert: He won.  For more details, including the full game, see this explanation on Wikipedia here.


3. The Card Game Delphi

In 1956, Bob Abbott invented Eleusis, a card game involving inductive inference.  While the game itself was highly original, the scoring system was somewhat arbitrary.  In 1962, my father devised the game Delphi, which, according to Martin Gardner, made several important improvements, including a much more logical scoring system.  While it solved the scoring problem, Delphi turned out to be less fun to play than Eleusis.  Later, Bob Abbott created an improved version of Eleusis called New Eleusis, which, unfortunately, still did not completely solve the scoring problem.
For the rules to Delphi, see this article in Denexa Games here.

4. The Kruskal Count

My father invented a card trick, called the Kruskal Count, with the unique characteristic that the magician never touches the deck of cards during the performance.  To make this plausible, he would claim to the audience that he was psychic.  There are various YouTube videos demonstrating and discussing it.  Shortly after devising the trick, my father, brother, and I visited a young married couple.  My father performed the trick several times on the husband, who kept accusing his wife of secretly colluding with him.  She was insulted and kept denying it\(-\)truthfully. Finally my father said to the wife, Well, the cat’s out of the bag.  You have been in on it all along, and you can admit it now. (She hadn’t.) My brother and I (both teenagers) thought it was hilarious; I doubt the couple did.

The trick turned out to have serious applications: According to Wikipedia, the underlying phenomenon has applications in cryptography, code-breaking, software tamper protection, code self-synchronization, control-flow resynchronization, design of variable-length codes and variable-length instruction sets, web navigation, object alignment, and others. There are various YouTube videos demonstrating and discussing it.

The Kruskal Count was featured in an episode of NUMB3RS, which Gasarch blogged about here.

5. Surreal Numbers

My father had a lifelong fascination with infinity starting in childhood, which deepened when he read Donald Knuth’s introductory book on surreal numbers.  For more about his interaction with Knuth after reading the book, see this blog entry here.  Wikipedia provides a concise explanation on my father’s webpage about surreal numbers and his contributions.  The entry highlights important results\(-\)both positive and negative\(-\)by Ovidiu Costin, Philip Ehrlich, and the mathematical logician Harvey Friedman (see here and here for the papers).

Martin's website has the following passage, which captures the issue beautifully.

Surreal numbers, which are defined constructively, have all the basic properties and operations of the real numbers.  They include the real numbers alongside many types of infinities and infinitesimals. Kruskal contributed to the foundation of the theory, to defining surreal functions, and to analyzing their structure.  He discovered a remarkable link between surreal numbers, asymptotics, and exponential asymptotics. A major open question, raised by Conway, Kruskal, and Norton in the late 1970s, and investigated by Kruskal with great tenacity, is whether sufficiently well behaved surreal functions possess definite integrals.  This question was answered negatively in the full generality, for which Conway et al. had hoped, by Costin, Friedman, and Ehrlich in 2015.  However, the analysis of Costin et al. shows that definite integrals do exist for a sufficiently broad class of surreal functions for which Kruskal's vision of asymptotic analysis, broadly conceived, goes through.  At the time of his death, Kruskal was in the process of writing a book on surreal analysis with O. Costin.

6. Alpha-Beta Search

While in graduate school, I came across Donald Knuth and Ronald Moore's paper on alpha-beta search (see here).  They posed the question of what is the expected branching factor in a game tree with \(c\) children per node and depth \(d\), and uniformly distributed values at the leaves.  They gave a partial solution.  Gerard Baudet found a recurrence for this value and improved the bound (see here).  This was the kind of asymptotics that my father excelled at, so I asked him if he could solve the recurrence.  He solved it by finding an asymptotic value for the number of leaves evaluated.  Right after that Judea Pearl published the asymptotic value for the branching factor (see here).

At the time I figured that the original question had been answered by Pearl, so the stronger result was not interesting.  A more mature version of me might have pursued it.  In reality, answering the original question is interesting, but for a number of reasons any further improvement is not particularly interesting, so I was probably right to drop it even if for the wrong reasons.  Unfortunately it was in the file drawer lost during the move to our new building, but if anyone cares I think I remember the exact high order term.

7.  Public Key Crypto

When he learned about public key cryptography, he invented his own system based on quadratic mapping just to understand how it works.  He gave a talk on it in 1983. He showed it to Ron Rivest who said that it was not secure. Oh well.

Practical consequences of RH ?

When it seemed like Riemann Hypothesis (RH) might be solved (see Lipton-Regan blog entry on RH  here and what it points to for more info) I had the following email exchange with Ajeet Gary (not Gary Ajeet, though I will keep his name in mind for when I want to string together names like George Washington, Washington Irving, Irving Berlin,  with the goal of getting back to the beginning) who is an awesome ugrad at UMCP majoring in Math and CS.

Ajeet: So Bill, now that RH has been solved should I take my credit cards off of Amazon?

Bill: I doubt RH has been solved. And I think you are thinking that from RH you can prove that factoring is in P. That is not known and likely not true.

Ajeet: What are my thoughts and why are they wrong?

Bill: What am I a mind-reader?

Ajeet: Aren't you?

Bill: Oh, Yes, you are right, I am. Here is what you are confusing this with and why, even if you were right you would be wrong.

Ajeet: It just isn't my day.

Bill: Any day you are enlightened is your day. Okay, here are the thoughts you have

a) From the Extended RH (a generalization of RH) you can prove that PRIMES are in P. (This algorithm is slow and not used. PRIMES has a fast algorithm in RP that people do use. Primes was eventually proven to be in P anyway, though again that is a slow algorithm). Note- even though we do not know if ERH is true, one could still RUN the algorithm that it depends on. ERH is only used to prove that the algorithm is in P.

b) There was an episode of Numb3rs where they claimed (1) RH implies Factoring in P-- not likely but not absurd (2) from the proof of RH you could get a FAST algorithm for factoring in a few hours (absurd). I say absurd for two reasons: (i) Going from basic research to application takes a long time, and (ii) See next thought

c) If (RH --> factoring easy) then almost surely the proof would present an algorithm (that can be run even if RH has not been proven) and then a proof that RH --> the algorithm's run time is poly. But I wonder -- is it possible that:

RH--> factoring easy, and

The proof does not give you the algorithm, and

 if you had a proof  or RH then you COULD get the algorithm (though not in a few hours).

I doubt this is the case.

Ajeet: So are there any practical consequences of RH?

Bill: Would you call better bounds on the error term of the prime number theory practical.

Ajeet: YES!

Bill: GREAT! For more on RH see here

Interesting Probability on a VERY OLD TV show

I have posted about things I see in TV or Movies that are math or CS related:

Do TV shows overestimate how much a genius can help solve crimes or make really good crystal meth which seems to be blue. YES, see here

Do TV shows get math wrong. YES, see here and about 90% of the episodes of Numb3rs

Closer to home- do TV shows say stupid things about P vs NP. Elementary (one of the two Modern Day Sherlock Holmes shows did) does  see  here

Did Kirk and Spock really defeat a computer by a trick that wouldn't work now. Yes, see Lance's post on this here

Do TV shows use the word Quantum incorrectly? They do but they are not alone as such, see here

Do people writing Futrama get their math right! Yes- see here

Do people writing 24 get their math wrong! Yes- see here

Does the Big Bang Theory mostly get things right? Yes! - see here

There are more (Seinfeld things comedians should learn proofs! Really- see here) but I can make my point just with the ones above.

ALL of the TV shows except Star Trek were from after 2000 (or so).  So, with the exception of Science Fiction, math-refs and sci-refs in TV shows are relatively recent- I had thought.

Which is why I was surprised and delighted to see, an episode of the old western (anti-western? satire of a western?) Maverick, from 1958 (before I was born!), called Rope of Cards a CORRECT and INTERESTING  math reference.Maverick bets that a random 25 cards from a deck of cards can be arranged into five  5-card pat hands (I had to look that up-- hands where you don't want to discard any cards, so  flush, a straight, a full house would qualify. 4 of a kind would be pat if there were no wild cards).  The sucker takes the bet and loses. Maverick later says the odds are high and called the game Maverick Solitaire.And that is now the name of the puzzle- see here. The prob is around 0.98.

I call this a mention of math since it has to do with probability- which may be a stretch. And I doubt the scene would encourage people to go into math. But it might encourage one to learn probability either to sucker others or to not be suckered.

So the question now is- are there other non-science-fiction, refs to math in older TV shows?
I suspect yes - similar to the one above which is gambling and probability. What is the earliest mention of math on a TV show? The oldest that did not involve science fiction or gambling?

When did Mathematicians realize that Fermat did not have a proof of FLT?

I recently came across the following passage which is about  Fermat's Last Theorem (FLT).

Pierre de Fermat had found a proof, but he did not bother to write it down. This is perhaps the most frustrating note in the history of mathematics, particularly as Fermat took his secret to the grave.


AH- so at one time people thought Fermat DID have a proof of FLT.  That is, a proof using just the math of his time, likely a very clever proof. I doubt anyone thinks that Fermat had a proof in this day and age. Actually it has been in fiction: in a 2010 episode Dr. Who episode The eleventh hour, the doctor has to prove to some very smart people that they should take his advice. He does this by showing them Fermat's proof of FLT. Good Science Fiction but highly unlikely as Science Fact. In an episode of ST-TNG  (Title: The Royale. Year: 1989) it is claimed that FLT is still open. Whoops. But in an episode of ST-DSN (Title: Facets. Year: 1995) they refer to `Wiles proof of FLT'.

Wikipedia states: It  is not known whether Fermat had actually found a valid proof for all exponents n, but it appears unlikely. I think that understates the case.


So here is a question for all you math historians out there: When did the math community realize that FLT was really hard?

We have one clue- the quote I began with. Its from... 2013. Whoops. The book is  The Simpsons and their mathematical secrets by Simon Singh (Author of Fermat's Enigma  which is about the quest to proof FLT).  I've read the passages about FLT in the Simpsons book over again to make sure he doesn't someplace say that Fermat prob didn't have a proof. No--- he seems to really say the Fermat had a proof. So whats going on here? Possibilities:

1) I'm wrong. There are serious credible people who think Fermat had a proof and he talked to them; perhaps while working Fermat's Enigma. I find this unlikely- I have never, literally never,  heard of  anyone, not even math cranks, who think Fermat had a simple proof.  Some cranks think THEY have a simple proof, though even that seems far less common after FLT was proven.

2) I'm right. He didn't have anyone who was both serious and credible check his book. I find this unlikely. He has written Fermat's 't Enigma so surely he is in contact with people that are both credible and serious.

3) He did have someone check his book but thought the story was better the way he told it. (This was common on the TV show Numb3rs which never let a mathematical truth get in the way of a good story.)
I find this unlikely since a better way to say it is we'll never know if Fermat had a proof!

One problem with such mistakes is that it destroys his credibility on other math things he writes of. That info about Dr. Who I got from the book, but I suspect its correct. And the stuff about the math that appears in the Simpsons is checkable and seems correct. I give one example: in one episode you see in the background

3987¹² + 4365¹²= 4472¹²

which is correct on a calculator with only 10 digits of precision. Cute! But I have stopped reading any of the math history in the book for fear that I will get incorrect notions in my head.

However, back to my original question: Was there a time when people thought Fermat really had a proof?Was  there a time when people thought there was an easy proof? When did that change?

Crystal Math- What NUMB3RS and BREAKING BAD both get wrong

The TV show Numb3rs  had as a premise that a GENIUS mathematician
could help solve crimes. Is this true? I rather doubt you need a GENIUS-
though of course some prob, state, data mining,  the math behind forensics, and a few other things help. And it may help to know some number theory if a mathematician who is working on the Riemann hypothesis has his daughter kidnapped.  But I don't think you need someone on the level of Charles Eppes.

The TV show Breaking Bad  (see Honest Trailor for Breaking Bad and/or
Idiots Guide to Breaking Bad if you've seen the first 4.5 seaons at least)
has as a premise that a GENIUS chemist can make really good crystal meth. And as a by product it's blue. I know nothing about the crystal meth business; however a chemist friend of mine (who has never made the stuff) tells me that YES, being a careful chemist is good, and certainly better than a meth-head who is more likely to blow up his lab than to produce any, a GENIUS chemist would not be any better than a good chemist.

The TV show Elementary  (Sherlock Holmes in modern day New York) and many other shows (Monk, Perception, Psyche, The Mentalist, Columbo, and others I am sure) has as a premise that a GENIUS observer could help solve crimes. This may be more true then the above, but there are other tools available today (e.g., DNA).

All of these shows, and others, make the  FALLACY OF EXTRAPOLATION. Taking a good idea and extrapolating it to absurdity.

Here is a non-TV example: If blogging is part of my job, and I can deduct job expenses for Tax purposes, then I should be able to deduct the cost of the DVD's for Numb3rs that I bought because of this post.

Math on FUTURAMA and LAW AND ORDER:CI

MATH ON TV

FUTURAMA mentions the Banach-Tarski Paradox! In the June 23, 2011 episode Professor Farnsworth invents a Banach-Tarski-Dupla-Shrinker which takes a blueprint of an object (like a sweater or Bender) and some matter and then produces two smaller but otherwise identical copies of the original. The real Banach Tarski Paradox takes one object and produces two of the exact same type. The writers might have felt that was just a little too weird. See here for a full description of the episode. The episode aired on thursday, and today, Tuesday, a full description is on Wikipedia. This surprised me (so fast!) but did not surprise my great nieces and nephews.

LAW AND ORDER: CRIMINAL INTENT had its last episode Sunday June 26, 2011, thus ending a rather long running show which was part of a rather long running (and still running) franchise. Here is the whole list: Law and Order (1990-2010, 456 episodes), Law and Order: Criminal Intent (2001-2011, 195 episodes), Law and Order: LA (2010-2011, 22 episodes), Law and Order: SVU (1999-2011, 272 episodes, and still going), Law and Order: Trial by Jury (2005-2006, 13 episodes), Law and Order: UK (2009-2011, 26 episodes, and still going). 456 episodes is HUGE! Check out this list of long running TV shows. The list is only updated once a year This surprised my great nieces and nephews (so slow!) but did not surprise me.

I recall three episode of Law and Order:Criminal Intent that mentioned math. I am sure there are more.

In the episode Bright Boy there was a school for gifted children in math that tried to get 10 year olds to work on the Riemann Hypothesis. It was not clear if they wanted them to solve it as children (which seems absurd) or as adults later in life (not absurd but a real long shot). The reason I find it absurd that a 10 year old could solve RH is that cleverness and brilliance is not enough- you have to actually have learned a great deal of math, perhaps too much for a 10 years old to have learned. Problems that need lots of KNOWLEDGE really can't be solved by bright 10 years olds or amateurs, no matter how brilliant they are. (See here for a post of Lipton's about of when amateurs helped solve math problems.) Getting kids interested in math by having them work on RH is the opposite of using Math competitions. Lance and I discussed math competitions as a way to interest kids in math here. Which is better? Even if you get bright pre-high school students working on problems, having them work on RH would just lead to frustration. Are there math programs that have student work on real open problems? How about phony open problems (the mentor knows the answer ahead of time). Some REU's do this for College students, but is there anything like this for High School Students?

The episode Inert Dwarf involved a brilliant physicist who, for medical reasons, was in a wheelchair (modeled vaguely after Stephen Hawking). One point of interest: he had a password that was based on hard physics and hence uncrackable. Gee, I thought that you just need to make sure your password is (1) not a word in any language (2) long enough, and (3) used Upper Case (easy for ME), lower case, numbers, and punctuation symbols. Unless it was some sort of quantum system (the episode did not indicate this) I can't see how hard physics can make a password uncrackable.

In some episode this season (I forget which one) Goren (the detective) was given the following riddle by his psychologist: There are two doors and two guards. One of the doors leads to heave, the other to hell. One of the guards always tells the truth and one always lies. You get to ask one guard one question and then you must pick a door. Goren is supposed to some sort of genius who also knows a great deal of stuff so I'm surprised he didn't know it. In the last episode of the entire series, To the boy in the blue knit cap, he answers it correctly. I think that was supposed to be symbolic or meaningful or something, but I didn't see why. (Bad writing? I'm being dense?) (ADDED LATER- ACTUALLY GOREN ASKED THE PSYCHOLOGIST THE QUESTION WHICH MAKES MORE SENSE IN TERMS OF WHO-KNOWS-WHAT.)

Bright Boy and Inert Dwarf had the same problem that many TV shows have: If the real world fact do not make the plot work, the writers change the real world facts. Numb3rs did this with Math quite a lot.

Complexity Year in Review 2010

Complexity Theorem of the year goes to Ryan Williams for his exciting separation of NEXP from ACC⁰. The runner up is Arora, Barak and Steurer for their algorithm for unique games. Also some great progress on some of Bill's favorite questions including Arithmetic Progressions and the Erdos Distance Problem.

None of these papers got mentioned in the New York Times so the most notable paper of the year goes to Deolalikar's P ≠ NP. Many of you got upset that I didn't give this paper the respect it didn't deserve. I did appreciate the publicity the paper generated for our great open problem but the status of the P versus NP question remains: still open.

Last year we highlighted several new blogs. This year the trend is reversing as several theory bloggers have slowed down or stopped blogging. A few of our commentors got very ugly on our blog this year and finally we have given in to comment moderation, though we rarely block.

But social networking in the theory community continues on in other ways highlighted by the Theoretical Computer Science Q&A site. The SIGACT Facebook and Twitter pages have well over a hundred followers each.

The jury is still out on how a near complete change of NSF personnel and the fall elections will affect funding for theoretical computer science. We can always hope.

In this year I started a discussion on remaking STOC. The most popular thing I ever wrote is now this tweet. And don't forget my daughter Molly and her friend Danielle as NP and P.

Gone but not forgotten: Martin Gardner, Joseph Kruskal, Avner Magen, Benoît Mandelbrot, Robin Milner, Partha Niyogi, Sam Roweis and Numb3rs.

Thanks much to our guest posters: Daniel Apon, Paul Beame, Rance Cleveland, Ben Fulton, Josh Grochow, M.T. Hajiaghayi, Bernhard Haeupler, Nicole Immorlica, Subrahmanyam Kalyanasundaram, Clyde Kruskal, Michael Mitzenmacher, Rahul Santhanam, Aaron Sterling, Richard Taylor and Vijay Vazirani. We also thank guest photographer Evan Golub.

Looking forward to 2011 with the big FCRC meeting, learning the location for the Simons Institute for the Theory of Computing and just maybe I'll finish writing my P versus NP book (a bit more than half finished).

NEW math on Futurama

The Aug 19, 2010 episode of Futurama had NEW math in it! It also has some other math refs.

1. This website claims that Ken Keeler, one of the writers who has a PhD in math, devised a NEW theorem for use in the show. The theorem and proof are here. I do not know if it is new but it is correct and interesting.
2. Bender the robot had mind switched with Amy, so he was in a human body. In order to prove that he was really a robot he had to pass the reverse Turing Test.
3. Since PURE MATH lead to a solution of a PRACTICAL PROBLEM The professor exclaimed And they say pure math has no real applications!

This is the first time I know of where some new correct math was introduced on a fictional TV show. NUMB3RS often had new bogus math.

Both The Simpsons and Futurama have websites devoted to math refs in the show: Simpsons Math, Futurama Math.

It is not surprising that The Simpsons and Futurama have math refs since writers Jeff Westbrook, David X. Cohen, and Ken Keeler who write for these shows, are all math folk.

See these two prior posts for more on comedy and math.

The End of Numb3rs

Sunday marks the end of the TV series that deals with the numbers 4, 8, 15, 16, 23 and 42. Monday marks the end of the TV series called "24". But lets talk about Numb3rs, which CBS officially recently announced would not be renewed for next year and aired its last episode on March 12th. 

Back in December of 2004 I wrote a skeptical post on this new TV series announced by CBS about "a FBI agent who recruits his brother, a math genius, to help solve crimes." The show lasted a surprisingly long six seasons and this is the 17th of the our blog posts through the years that have mentioned the show. 

After a solid start, the series slowly devolved into a crime procedural where the math became more jargon than relevant. I admit that I stopped watching after a while but have since been catching up on DVD. I haven't seen the last season yet.

Theoretical computer science had several mentions on the show with algorithms from Dijkstra to Kruskal to Shor. In the second episode, the mathematician Charlie became obsessed over P versus NP. In the second season Charlie exclaimed to a purported psychic "Let's all sit down at the Ouija Board and try to solve P versus NP once and for all."

What I liked most about the show was the portrayal of the scientists, in particular the interactions between the mathematician Charlie (played by David Krumholtz) and the physicist Larry (Peter MacNicol). Their personalities and discussions seemed real, not unlike a various combination of academics I know (as opposed to say The Big Bang Theory).

Now that Charlie no longer needs to catch criminals, he can go back to being obsessed over P and NP, doing some real good in the world.

My last post on steretypes (I hope)

I was not going to post on stereotypes anymore (my last two posts were on the topic) but three events that span 100 years have inspired me to do to.

Event ONE: I found a blog that I posted in Aug 1909 which asked if the Americans might catch up to Europe in Mathematics someday. One of the comments on it was

Look at the German Mathematics Tradition!. Look at the American one. The Americans are so weak my comparison that it must be something about their culture. It is clear that the Germans have always been better than the Americans in Mathematics, and always will be. Will there ever be a American Hilbert? I think not.

EVENT TWO: I found a blog entry from Aug 1960 which asked if Japan might catch up to American in Engineering and Car Building. One of the comments on it was

Don't be ridiculous. The fact that the phrase Made in Japan has come to mean that it is of bad quality shows that the Americans are better Manufacturers than the Japanese and always will be.

EVENT THREE: In Aug 2009 I co-ran a TA orientation with ***SORELLE*** and another grad student ***MAH***. As part of it, everyone was to give me their name, what course they are TAing, what field of CS they want to study, and their favorite TV show. For the TV shows I got the following (probably more that I forget)

1. So you think you can dance dance dance dance dance.
2. Friends
3. The Big Bang Theory
4. ST-TNG and Babylon 5
5. Daria and Burn Notice (that was me)
6. Numb3rs (that was ***SORELLE*** who I respect in everything except taste in TV shows.)
7. Daily Show and the Colbert Report
8. I don't' watch TV since its just a mechanism to deliver commercials. (Gee- he could get NETFLIX and get commercial free DVDs.)
9. I don't watch TV.

There may have been a few more. However, the person who picked ST-TNG noted that I can't believe in a room full of CS Grad Students I'm the only one who mentioned a Science Fiction Show (READERS: picture this person in your mind.) The stereotype of CS people being Star Trek Fans is out of date. When the recent Star Trek Movie came out Lance posted an Obligatory Star Trek Post. I don't think it is obligatory.

Why has the link between Star Trek and CS been weakened? I think that both CS and Science Fiction have become more mainstream. Hence CS can overlap with non-Science Fiction and Science Fiction can overlap with NON-CS (actually it probably always did).

Back to stereotypes. The person who was the only CS Grad Student who mentioned a Science Fiction Show was a female. I suspect that is not the picture you had in your mind.

Math on the Simpsons Last Night

Last night on The Simpsons they had a math problem. Homer solved it! Since Jeff Westbrook (PhD from Tarjan) is one of the writers, and I've heard they have other writers with a math bend, I'm not too surprised that they had a math problem. I am surprised that Homer solved it. Its a problem you've probably heard in other forms:

Homer has with him Baby Maggie, his dog, and a jar of poisons that look like delicious candy. (Homer: Oh, why did I take my baby and my dog with me when I went to buy poison! And why do the poison has to look so delicious!?) He needs to get all three across the river. He can only take one of them at a time in his rowboat. He can't leave Maggie with the poison. He can't leave the dog with the poison. (He CAN leave Maggie and the dog.) How does he do this?

The Simpsons has had lots of math on it. There is a webpage of all math on The Simpsons here, though it doesn't have last night's episode yet (quite reasonable--- if you expect that then you expect to much from the digital age).

How does The Simpsons compares to Numb3rs in terms of the accuracy of the math presented? I suspect The Simpsons is more accurate; but, to be fair, they don't have to find some goofy math way to solve a crime every week. The math on Numb3rs, goofy as it sometimes is, does connect to some math of interest, see this web page.

If a Hobby relates to your work, is it a Hobby?

In yesterdays blog Lance mentions that he didn't see other math people or trade problems when he was on vacation, and that it wouldn't have been a vacation if he had.

This raises a question: Can you ever use a hobby in your work. I give a few examples below.

1. Steve Skiena wrote a book Calculated Bets about mathematical modelling and betting in sports. This combined Steve's lifelong hobby of watching and betting on Jai-Alai with serious math and computer science of interest.
2. Ken Regan's hobby is chess and he has some research there, as seen here.
3. My hobby is collecting novelty songs and I've gotten some blogs out of that. (Is blogging part of my job?) Other bloggers also use their hobbies on their blogs-- Luca and photography comes to mind.
4. Steve Rudich's hobby is magic, and I've seen him entertain at conferences. Some of the magic is based on math.
5. Lance has commented on the show NUMB3RS in the blog, and I wrote a reviewed Season 1 my SIGACT NEWS column. (If I buy the DVD and review it again, is that tax deducbible?)

If your hobby is some game then there may be some math of interest surrounding the game that you could get involved with research on. If your hobby is collecting paintings then you may have a harder time connecting it up with your work. (Maybe Game Theory of Auctions.) Do you even want to connect up your hobby with your work? Hobby is almost defined as not work.

Since most of us (I assume) like math, the line between hobby and work may be hard to see. If I work on Math problems in my leisure time, is that a hobby or work? If one of them inspires a paper then does it cease being a hobby? How does Sudoko fit into this? If I actually use the ZK Sudoko protocol to convince someone that I solved it, is that work or play?

Nerds

The Chicago Tribune wrote a feature on "nerds" in Tuesday's paper.

Nerds are perceived as authentic because they're unable to follow trends. Authenticity is always in–or a gesture toward authenticity is always in. Nerds are perceived as people who just have to pursue what they're interested in and ignore what's supposed to be cool.

Yeah "authentic," that's what I was in high school. Don't miss the photo gallery of fictional nerds. They forgot to mention the classic movie Revenge of the Nerds.

Fun fact: A nerd first appeared as one of the strange animals in the Dr. Seuss book If I Ran the Zoo. The expression was popularized by the Fonz on Happy Days, a popular TV show when I was growing up. Certainly I exemplfied nerddom in my high school (captain of the chess team, president of the computer club, ugly glasses and socially awkward). I grew out of it a bit, but anyone who writes (or bothers to read) this blog must have some nerdiness left within them.

Is being a nerd cool now? TV shows about nerds—Numb3rs, Chuck, Big Bang Theory, CSI—all got renewed. We have famous nerds like Steve Jobs and Bill Gates. But once nerds are cool, they are nerds no longer.

Math on TV

There was an episode of NUMB3RS (which starts its fourth season next Friday) that mentioned  the kruskal count. This is a card trick invented by Martin Kruskal. His son Clyde Kruskal is in my dept. Martin passed away in late December of 2006 and it is likely they put that reference in as a tribute. (See this and this for comments on the memorial service.) I watched the episode with Clyde. The good news is that YES, they did indeed mention The Kruskal Count and thats kind of cool seeing someone you know mentioned on NUMB3RS. The bad news is that the reference made no sense whatsoever. Here are two items that make as much sense as what they said.

1. The list of suspects looks random but we know that its not. To solve the case we use the Nisan-Wigderson derandomization technique.
2. We know the murder took place within this 5 block by 5 block area. We know that there were 10 people interacting to plan it. We can solve the case by looking at both the space and the interactions and then applying the Lund-Fortnow-Karloff-Nisan theorem that changes space into interactions.

If math you did was on a TV show, would you mind if they got it completely wrong? Personally, I would not mind that, I would be delighted (and surprised) to find my name on TV. A bigger issue- if it was a bad episode I really would not like that since I would probably want to show it to friends and family, and I would not want to subject them to bad TV. (The episode of NUMB3RS with Kruskal Counts was a terrible episode.) SUGGESTION: Take some math that you have done and see if you can find a way to make it fit into an episode of NUMB3RS It does not have to make sense, but it should sound like it does. (As I did above.)

Math Terms used in real life-good or bad?

Paul Beame's comment on my last blog ASK THE ALGORITHM, and one email comment that I got from someone who was hesitant to post since she thought people would ask if she was on crack, made the point that even if the ad campaign is misleading about what an algorithm is, it gets the word and concept out there, and this is all to the good. I tend to agree.

This raises the question: if a math or CS term is getting out there, even incorrectly, does it help the field? How incorrect? How much does it help? Examples:

1. On 24, season two, there was a line `we can't break in, its been Huffman coded!' This makes no sense mathematically but it raises awareness of security issues.
2. On NUMB3RS there are too many examples to count, but I'll pick my favorite: In Season one there was an episode where they claimed that once you solved the Riemann Hypothesis you could factor numbers and break various security systems EASILY. That is, the time from the proof being completed to the code cracking the systems would be less than an hour. While this is absurd, it does let people know that computer security can use some high powered math.
3. On a radio station I heard the DJ say

   Here at WCOZ we have an axiom, thats like a saying man, that weekends should be seven days long!

   I don't think this helps people understand what an axiom is.
4. A commercial once said

   And to prove we have the lowest prices in town we will give you a free camera for just visiting our store!

   Not the sense of rigor I want to instill in my students

Inductive Turing Machines

On last week's Numb3rs episode One Hour, Charlie, the mathematician, and Amita, his colleague/girlfriend, had the following conversation:

Charley (to Amita): I haven't seen an inductive Turing machine used like that before.
Amita: I'm trying to find the finite state machine for these. (points to screen)

So what is an inductive Turing machine? I put the question to Bill Gasarch.

If you IGNORE the TV show, it could mean the following, taking a cue from the field of Inductive Inference:

A set of computable functions S is in EX if there is a TURING MACHINE M such that for all f in S if you feed f(0), f(1), f(2), … into M, it outputs e₁, e₂, e₃, … and in the limit the sequence converges to e, a Turing Machine index for a machine that computes f. Such a machine M is called an INDUCTIVE TURING MACHINE.

Does this definition make sense in context of the show? The set S of regular languages (those computed by finite state machines) is in EX, where e_i is the lexicographically least FSM whose output is consistent with f(0), f(1), …, f(i-1).

Of course this is an incredibly inefficient way to learn regular languages, but then again Amita wasn't having much success. Perhaps she should have used one of the efficient finite automata learning algorithms like Rivest and Schapire.

Gasarch has a different take.

The show DID NOT mean this. So what did they mean and what could they have said? They should have either used a generic term for learning or just use a fictional term. Then they can't really be wrong. Here are some possibilities:

1. Charley (To Amita): I haven't seen that learning algorithm used that way before.
2. Charley (To Amita): I haven't seen Carl Smith's Technique used that way before.
3. Charley (To Amita): I haven't seen cross-convergence used that way before.

Or they could have made Charley's comment and Amita's Answer match better:

Charley (To Amita): I haven't seen the Generalized Polynomial Hales-Jewitt Theorem used that way before.
Amita: I'm trying to prove the polynomial van der Waerden's theorem over the reals.

The conversation they DID have is connected to later in the show when they are trying to learn the maze. I can make a vague connection–the show did not do so.

Having said all that, it was a good episode.

By the way you can watch Numb3rs on-line for free.

Entertainment Tidbits

Can a CS degree propel you to a major acting role on a popular new TV series? Worked for this person.

I heard a complaint that in the movie Deja Vu they used face-recognition algorithms to find a suitcase in a large city in a matter of seconds. Because it's important to keep the computer science accurate in a time-travel movie.

In the last Numb3rs, Charlie the mathematician was seen carrying a copy of the SIAM Journal on Computing, a prominent TCS journal. Was he reading my paper or yours? At the end of the episode Larry the physicist left on the space shuttle to spend six months on the International Space Station while the actor, Peter MacNicol, moves over temporarily to the show 24. Couldn't Larry just have gone on a normal sabbatical?

On a more serious note we finally got around to watching Al Gore's documentary An Inconvenient Truth. Gore seriously impressed me with how he laid out the arguments and effects of global warming. The movie really affected my daughters leading to some interesting family discussions about warming and what we can do. I highly recommend watching the movie for those who haven't yet done so.

Numb3rs of Collaborators

Last week's episode of Numb3rs The Mole had a mildly interesting academic side story. [Mild Spoiler Warning] Charlie, the mathematician, discovered that his friend Larry, the physicist, published a paper without asking Charlie to collaborate on the math, which according to Charlie would make the paper go from "very good" to "great". Larry later confessed to Charlie's dad that he worried too much about relying so much on a single collaborator, especially one so busy helping his brother at the FBI. Eventually Larry and Charlie talked out their issues and agreed to work together again.

In the real academic world you rarely see two people collaborate almost exclusively over a long period of time. We all have certain people with whom we collaborate often because we have similar interests, complement each other's skills, or simply that we work well together. But having a single collaborator can lead to narrow research, using the other as a crutch and worrying that outsiders won't know which one is the stronger researcher. But most importantly we thrive on variety and having different collaborators keeps research exciting.

Another Approach to P ≠ NP

Last week's Numb3rs episode "Mind Games" centered on a purported psychic causing the mathematician Charlie Eppes to exclaim "Let's all sit down at the Ouija Board and try to solve P versus NP once and for all."

A Second Helping of Numb3rs

I've been catching up on my Tivo on the second season of Numb3rs, the CBS television series about a math professor Charlie Epps who uses math to help his brother at the FBI.

Most of the episodes this season do a nice job explaining mathematical concepts including several relating to theoretical computer science (see below), though the connections between the math and the plot get more and more tenuous.

A couple of Numb3rs related web sites give more details on the mathematics described in the show. Texas Instruments created a site giving high school level descriptions and activities on the topics discussed in the show including Voronoi Diagrams, Entropy, Eulerian Tours, Steiner Trees, Error-Correcting Codes, The Art Gallery Problem and Pseudorandom Numbers. Also, a Northeastern professor writes a weblog giving more detailed mathematical explanations of the topics on the show.

In my favorite episode of the season Convergence, a rival mathematician gives a talk finding a hole in the proof of the Epps Convergence, Charlie's best work. This causes Charlie to go through an introspective phase questioning whether his FBI work keeps him away from doing his real research as a mathematician. He considers the importance of being a mathematician while being part of a larger world, philosophical issues that many real mathematicians also contemplate.