The Dream

I have this theory that everybody's notion of "recent history" starts not from their memories but from their birth date. Case in point: Billy Joel's We Didn't Start the Fire. The first major event of my then very young life came from an oppressed people making their voices heard. The newspapers in the early days of my life were full of fear of violence that might come from the upcoming march on Washington. But 200,000 souls came out fifty years ago today in a peaceful demonstration asking for the basic freedoms the rest of America had.

Having moved to the birthplace of Martin Luther King, Jr from the hometown of the first black president, I know much has improved in the last fifty years. But we know King's dream is far from fulfilled, obvious to us from the paucity of African-Americans in our conferences and classes.

Take a moment of your day, watch the greatest speech of the 20th century, and remember how far America has come, and how far America has yet to go.

What are Galois Games?

How are math concepts named?

1. After the people who was involved with it. Examples: The Cook-Levin Theorem, Goldbach Conjecture, Ehrenfeucht-Fraisse games,
   Banach-Tarski Paradox.
   
2. A descriptive name:
   Examples: Chromatic Number; Girth of a graph (length of shortest cycle). This resembles the definition of Girth in English though I have only heard the word used in mathematics;
   Duplicator-Spoiler games.
   
3. A name that conjures up a nice image. Examples: Dining Philosophers problem;
   The Monty Hall Paradox (though future historians will think he was a great Probabilist).
   
4. Name may have very little connection to the concept. Example: The Pell equation.
   

I saw an article whose title was Greedy Galois Games. I wondered what this game could be.

1. Do the players alternate picking polynomials and if the composition is solvable by radicals then (say) Player I wins.
   
2. Did Galois invent some game?
   

The first game I thought of might be interesting; however, the paper was not about that. Nor was it about some game Galois invented. So---what is a Galois game? Aside from being a mathematician what else is known about Galois:

He died in a duel!

In the article Greedy Galois Games they study a DUEL between two BAD DUELISTS. The idea is that if both have prob of hitting p (and p is small) and they want to make it fair, first Alice shoots, then Bob shoots the min number of times so that the prob of Bob winning exceeds Alice's, then Alice shoots a number of times so that her prob of winning exceeds Bob's, etc. The paper ends up involving the Thue-Morse sequence. They are NOT using the name Galois the way we use Banach in Banach-Tarski Paradox, nor the way we use Monty Hall in The Monty-Hall Paradox. The fact that Galois was a mathematician has nothing to do with the naming,  The authors are using  Galois because he is a  famous duel-loser. They could have used Alexander Hamilton (who lost a Duel to Aaron Burr) and then called them Greedy Hamiltonian Games, in which case I would assume that the game involved
Hamiltonian cycles or Quaternions.

P = NP and the Weather

In the Beautiful World, my science fiction chapter of The Golden Ticket where P = NP in a strong way, I predicted that we could predict weather accurately enough to know whether it will rain about a year into the future. Besides putting Novosibirsk on the wrong side of Moscow, my weather prediction prediction has drawn the most ire from my readers.

Here was my thinking: Weather forecasting comes down to modeling. Find a good model, use the current initial conditions and simulate the model. P = NP can help dramatically here by making what should be the hardest part, finding the right model, easy. P = NP would help create much better models and should lead to far more accurate and deep forecasts than before. A year ahead prediction of weather didn't seem out of the realm of possibility.

As my readers point out, one cannot put in all of the initial conditions which would involve too much data even if we could get it, and small random events, the so-called butterfly effect, could dramatically change the weather in even a short period of time. Dean Foster, a Penn statistician, wrote me a short piece giving an analogy to a game of pool over time changed by the gravity generated by a single proton.

So how far can you predict the weather if P = NP? A month? Of course we'll probably never find out since I doubt P and NP are the same. In retrospect I shouldn't have put in such an aggressive weather forecasting because it detracts from other great things that happen if P = NP such as curing cancer.

When Lance was 10 years old..

In honor of Lance's 50th birthday I ask the following: When Lance was 10 years old which of the following were true?
(Disclosure- some of the below are from a birthday card.)

1. A REMOTE meant a secluded spot off the beaten path.
   
2. CABLE was something that supported a bridge.
   
3. A VIDEO GAME was trying to make out what fuzzy images were on a snowy black and white 10 inch TV screen.
   
4. A CELL PHONE was what you used to make one phone call from jail.
   
5. A CALCULATOR was the accountant who did your parents taxes.
   
6. AN AIRBAG was someone who talked too much.
   
7. DIGITAL COMPUTING was counting on your fingers.
   
8. HIGH SPEED ACCESS was an on-ramp to the freeway.
   
9. SURFING was something done on a board in the ocean.
   
10. A BIRTHDAY was something Lance looked forward to.
    
11. A MOUSE was something you didn't want in your house.
    
12. A SPAM ASSASSIN was someone who killed people by giving them poisoned spam.
    
13. A WEB was what spiders wove.
    
14. A BUG was what spiders ate.
    
15. AMAZON meant where some big rain forest is (smaller now).
    
16. GOOGLE was an obscure term used by some math folks for the number 10¹⁰⁰.
    
17. BING had no meaning.
    
18. APPLE was either a fruit or the record company founded by the Beatles. (There really WAS a legal name-issue when Apple-the-computer-company got into music see here .)
    
19. It was impossible to have 10,000 friends.
    
20. There were only three Network channels and a few local ones.
    
21. Music was on Vinyl records.
    
22. You went to the bathroom during commercials.
    
23. Johnny Carson joked that couples had sex during commercials on his show. (Ask your grandparents who Johnny Carson was, what commercials were, and what sex was.)
    
24. People read books written on paper.
    
25. Computer Science was not available as a major at most schools.
    
26. When people said you sound like a broken record they actually knew what a broken record sounded like.
    
27. People really would DIAL a phone number.
    
28. People would have to actually stop at toll booths instead of using easy-pass.
    
29. Long running TV shows would have one (or at most two) Christmas episodes since there were no arcs, hence an episode could be inserted into any season at any time. Contrast: M*A*S*H in its 11 seasons and 256 episodes had TWO Christmas episodes, where as 30 ROCK its 7 seasons and 131 episodes had FOUR Christmas episodes. (This may be THE least important consequence of the new technology.)
    
30. There were bar room fights over trivia since you couldn't just look it up on Google. The Guinness Book of World Records was supposed to cut down on bar fights, but it didn't quite work.
    
31. People knew how to read maps and get a sense of where things were instead of relying on technology. That's why today the number of hikers who get lost has skyrocketed.
    
32. If MTV existed they would still be playing music videos. The question Why doesn't MTV show Music Video's anymore has been asked so often it is now Cliche. But the above video provides an answer.
    
33. Lance did not recognize the importance of NP-completeness. Then again, neither had the math community, the non-theory computer science community, and Probably parts of the theory community.
    
34. To find out what time it was you couldn't look at your cell phone, TV set, or Microwave. You had to go outside and look at your sundial.
    
35. TV shows may have pilot episodes, or may not, but they didn't bother with explaining everything. Thought experiment: If Mr. Ed was on today
    they would explain how he could talk (A government experiment gone wrong? gone right?) rather then the ONE line by Mr. Ed in the first episode: Don't try (to understand why I can talk)--- its bigger than both of us.
    
36. We all watched a TV show the same night. Contrast- last month I watched Firefly.
    (If you are a fan of firely check this out.)
    Bizarre result of this--- since people can't find people to talk about shows as much as the used do, there is now a show called TALKING BAD where people on the show TALK ABOUT Breaking Bad
    
37. The final Jeapordy theme music didn't have lyrics. Now it does: here.
    
38. When you heard a mnemoic device like Kids Prefer Cheese Over Fried Green Spinach it was hard to find out what it meant- now its easy (just use Google!)
    

True story: On March 9, 1967 John Smith (not his real name) wanted to watch Star Trek (Episode: Devil in the Dark) but his parents wanted to take the family out for dinner. So he pretended to be sick so he could watch it- because, as he puts it, if I don't see it now I will NEVER GET TO SEE THE EPISODE, EVER!!!!!. Imagine a world without DVR, DVD, TIVO, On-Demand, Hulu. He doesn't have to imagine it. Our younger readers do.


I think SURFING, MOUSE, and SPAM really have changed primary meanings. FRIENDS may have also.

Flash Gordon

We watched the movie Ted last week but this post isn't about that movie. The movie has several references to the 1980 movie Flash Gordon including an extended cameo by Sam Jones who played Flash.

Flash Gordon and its soundtrack from Queen saved me senior year of high school--whenever I felt down I would listen to the album and run the movie through my head escaping reality for a little bit. These were the days before videos and CDs, now I've rewatched the movie several times on DVD.

Flash Gordon was not a great movie by any means but it resonated with me with its action sequences, great music and corny lines like "Flash, I love you, but we only have fourteen hours to save the Earth!". The stars of the movie Sam Jones and Melody Anderson were and still are relatively unknown but it had a great supporting cast.

Topol, best known as Tevye in Fiddler on the Roof, played a scientist who many mocked for his crazy (but true) ideas of what was happening in outer space. Basically the same character as when he played Galileo.

Timothy Dalton played Prince Barin and would go on to be James Bond and the Max von Sydow, who played chess against Death in The Seventh Seal, was the Ming the Merciless.

What does this all have to do with computational complexity? Absolutely nothing. But today I turn 50, it's my party and I'll post what I want to.

How much Trig does your governor know?

How much math should our public officials know? Basic probability and statistics so they can follow the arguments that their science advisers give them. And they should hire good objective science advisers and listen to them.

How much Trigonometry should a Governor know? Should a Governor know the angles of a 3-4-5 triangle? The following true story is paraphrased from Somewhat more than Governors need to know about Trigonometry by Skip Garibaldi.

In June 2004 Governor Jeb Bush of Florida was giving a talk to promote state-wide annual testing of students in public schools. A high school student asked him What are the angles in a 3-4-5 triangle? He responded I don't know. 125, 90, and whatever is left to add up to 180. Note that (1) he knew that 3-4-5 triangle has a 90 degree angle, (2) he knew that the angles of a triangle add up to 180, but (3) he didn't realize that 125+90 > 180. Still, I suspect most governors would do worse. The real answer is 90, 53.1 (approx), 36.9 (approx). A retired math professor was later quoted as saying I would not expect many mathematicians to know that.

The paper then proves the following:

The Governors Theorem: If a right triangle has integer
side lengths then the acute angles are irrational when measured
in degrees.

When politicians say things that contradict current science (e.g., on evolution or global warming) I wonder if they know the truth and are lying to please their voters, or if they honestly don't know the truth.I also wonder which one is worse. In the case above I think Jeb honestly didn't know, and that's fine.

Don't Have an End Game

As a young professor, I wrote a grant proposal and took it to a senior theory professor for comments. He told me to take out the line "The ultimate goal of computational complexity is to settle the P versus NP problem." He agreed with the line, he just said that if we make these claims to the NSF then what happens after someone proves P different from NP? Nothing left to fund in complexity.

There was precedence here. In the 70s and 80s algebraists had the great goal of classifying all the finite simple groups. Once they were done, then what? Other examples are sending a man to the moon in the 60's or having a computer that beats the best human chess player.

Having an ultimate goal can be very motivating but quite limiting if that goal is actually reached. Luckily for us the P versus NP problem is a goal which will not likely be reached for a very long time.

Longest time between posing a math problem and it being answered?

(We were asked to remind you: ITCS 2014 Call for papers: call for papers.)


What problem in math had the longest time between POSING IT and SOLVING it? This might not be a well defined question since the notion of when was it posed? might be murky. For some problems even when it was solved? might be murky. Nevertheless I have a candidate:

Is there a straight-edge and compass construction that will, given a square, produce a circle with the same area. (This problem is often called Squaring the circle..)

Wikipedia says that Oenopides was the first person to pose construction problems and that he posed this one. He was born in roughly 500 BC. Even back then there were people who thought it could not be done. However, it was proven impossible when pi was shown to be transcendental in 1882 by Lindemann. (This was one of the motivations for Lindemann.)

This problem was open for roughly 2300 years.

1. Is there any solved problem that was open for longer?
   
2. Is there any open problem that has been opened for that longer?
   
3. If you polled people in 400 BC what they would have guessed for which way it would go and when it would be solved?
   

Will P vs NP take that long?

Why is Multiplication Hard?

Quick. What is 879544 * 528045? Unless you used a calculator or was some sort of savant you it would take you a couple of minutes to figure out a solution. Of course a computer can calculate this very quickly.

But what a computer can't do easily is learn how to multiply. If we feed in triples of numbers, (879544,582045,464438811480),  (541535,711245,385164061075), (230589,481621,111056504796), ..., into any machine learning algorithm it's doubtful the algorithm could take a new pair (666750,313009) and produce its product 208698750750. For if it could, then we should be able to use a similar algorithm to figure out how to factor numbers, which we believe a computationally difficult talk.

When you look at what machine learning seems to do moderately well: spam detection, face recognition, language translation, voice-to-text and self-driving cars, these are things that humans with a reasonable amount of training, can do very well.

Is this some philosophical argument that our brain works like machine learning algorithms? Think of it more as an observation.