Types of questions for exams

QUESTION: Give as many types of exam questions you can, give examples, and comment on if this is a good type of question.

My answer below.

1. A problem that some students can get right even if they never had the course because they have seen it in some other course. EXAMPLE: In a course on Ramsey Theory have a question that uses the Prob. Method. PRO: The question is still in scope for the courses. CON: A bit awkward that someone may have learned the material elsewhere. UPSHOT: This is FINE.
   
2. A problem that some students can get right even if they never had the course because they are quite clever. EXAMPLE: Easy Combinatorics or Probability in a sophomore Discrete Math Course. PRO: The question is still in scope for the courses. CON: A bit awkward that someone may have missed class but still got it right. UPSHOT: This is FINE.
   
3. A rigged question--- students saw two examples in class, two examples on the HW and now have to do one themselves. EXAMPLE: proving numbers irrational. PRO: Clearly in scope and fair. PRO: They will surely understand what you are asking for. CON: They may get it right via memory rather than understanding (they may not even know the difference.) UPSHOT: This is FINE though it requires some planning ahead of time.
   
4. A rigged question with a twist--- students saw two examples in class, two examples on the HW and now have to do one themselves but its DIFFERENT in an important way. EXAMPLE: In class and HW do many problems like Here is the distribution, here is a random var, what is its expected value but on the exam give Here is a random var, here is what we want for the expected value, give a distribution that gives us that. PRO: Harder to memorize template. CON: May be hard to grade as they say odd things. CON: May be confusing to know what you are asking for, even for good students. UPSHOT: This is FINE though it requires some planning ahead of time.
   
5. A problem that requires utter mastery of the material but no creative thought. EXAMPLE: Give the algorithm (that we did in class) for proving that a CFG's are in P. Write it up so that someone who had never seen it can understand it. PRO: Straightforward yet hard to get via memorization. CON: Might be too time consuming for an exam. CON: (From experience) no matter how much you say in bold letters things like Write it up so that someone who had never seen it can understand it. They will skip steps and write it up badly and its hard to tell if THEY really know it. UPSHOT: I do this but only in certain cases.
   
6. A problem that requires them to be creative (this is ill defined but its the opposite of the one above). PRO: If they truly understand the material they can do this. CON: My PRO may be incorrect. UPSHOT: Absolutely fine for HW which are not worth much for the grade anyway and I can enlighten them. I tend to avoid these on exams. Though the line between creativity and standard is a thin one. (Problem for an exam: How thin in millimeters?)
   
7. A giveaway question. When I teach Formal Lang Theory I have (going back to when I was Harry Lewis's TA in 1981) have on the exam Give an example of a string of length 4 over the alphabet {a,b}. An unintended consequence- if they CAN"T do this its a really bad sign. I have asked this question many times and I have literally NEVER seen someone get it wrong and pass the course. I have gotten the following answers: ab*, ababa, and a DFA recognizing aaaa (that I was tempted to give credit to but did not). Incidentally, the most common right answer has always been abab. Second is abba. PRO: I have this one early in the exam to calm them down.
   

I try to ask some of each type on an exam. However, sometimes a question can be easier or harder than you intended, or be harder to grade then you thought, or not be in category you thought it would be in. The hardest line to draw is which questions are a matter of mastery and which are a matter of creativity? Another issue- some students can abstract better than others.

When teaching a large course such as Sophomore discrete math (150-200 students) I tend to get a uniform distribution skewed a bit on the high side. More precise: I tend to get at roughly 10 students in EVERY 10-point interval: 0-10, 10-20, 20-30,..., 90-100, with less on the low side and more on the high side. The benefit of this is that the students who get (say) less than 40 CANNOT say Well--- everyone did badly. They really are send a signal to either work harder or drop (I tell them this directly as well). I don't understand profs who give exams where nobody cracks 50/100 (I have heard this is common in Physics). They are wasting half of the grade spectrum.

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.

Certifying primality in a CONSTANT number of operations

For this post I will only count the operations PLUS, MINUS, MULT. They may be done on rather large numbers.

Recall that from the work coming out of Hilberts 10th problem we know the following: For every c.e. set (used to be called r.e., some people still do) there is a polynomial f in 13 or less variables (we'll assume 13) with coefficients in the integers such that

x in A iff (∃ a1,...,a13))[f(x,a1,...,a13)=0]

In an article about Hilbert's 10th problem written in 1974 by Davis-Matiyasevich-Robinson they note that by this result there is a FINITE number M such that, for ALL primes p, there is a certification that p is prime that uses at most M operations: given p a prime let a1,...,a13 be such that f(p,a1,...,a13)=0. The certification that p is prime is just the evaluation of that polynomial and seeing that its 0.

Is this still the only proof that one can certify primality in a CONSTANT number of operations?

Primes is irrelevant to all of this--- any c.e. set would work. (The result for c.e. sets may qualify as a theorem that is less interesting because its more interesting.) But for primes I am wondering if there is another way to do this- perhaps using number theory, perhaps with a smaller value of M. For the explicit poly for primes, due to Jones, see here.

Ph.D. Attrition

Leonard Cassuto writes in the Chronicle an article Ph.D. Attrition: How Much Is Too Much? He presupposes the answer with the subtitle "A disturbing 50 percent of doctoral students leave graduate school without finishing".

The 50% goes over all fields but the numbers in computer science are somewhat in that range. Computer Science has different issues than humanities and theoretical CS has not quite the same issues as the rest of CS. Certainly we lose several students to start-ups and high-paying jobs. But what about the ones that just have trouble in grad school.

Cassuto writes

Perhaps they lack the temperament to work on their own (which undergraduate work does not test as severely as graduate school does), or perhaps they lack, say, the mathematical chops necessary to succeed at advanced physics. But there will be a number—and if admissions committees do a good job, it will be very small—who won't be able to finish because they're not up to the demands of the task.

Having read through many graduate applications through the year there are very few, perhaps on average one or two a year, that will clearly succeed through graduate school. Almost without exception those students go to MIT or Berkeley.

For the rest of us, you have a choice. You can either take someone who will probably work their way to a Ph.D. but with uninspired research, or those you can take a risk with a student who might have strong potential. Some of those students become great scientists, some of them flame out. You get a higher attrition rate by taking risks but that's not a bad thing.

If you do take a risk in admissions you need to encourage students to "pursue other opportunities" once you realize they won't make it. That's a process that too many of us try to avoid, so we don't take those risks as much as we should.

I gave a poster session at Erdos 100- so how did it go?

In a a prior post I suggested that STOC perhaps have people give posters instead of talks. While I doubt this will ever happen I think its worth thinking about, especially for future conferences that may be founded. I also noted that the NIPS conference they do this.

But enough theory- at the Erdos 100th I GAVE a poster. Here are my thoughts.

1. The paper I did a poster I posted on here and I posted to arxiv here. A bit awkward in that it was submitted to ERDOS 100 as USING THE ERDOS-RADO CAN RAMSEY THEOREM ON A PROBLEM ERDOS ASKED AND A PROBLEM ERDOS SHOULD HAVE ASKED, but by the time the conference came I had much better results (due mostly to co-authors of which I went from 1 to 4) and no longer used ERDOS RADO CAN RAMSEY. Do I do the Poster on what was submitted or what I have now? I picked a very nice proof to concentrate on for the poster that was new but still in the spirit of what was submitted. (The final version is being written- I'll post on this blog about it later.)
   
2. The posters were for TWO days, for TWO hours after lunch. Since it was after lunch they didn't serve food. This seemed to work. They were in two shifts-- some did Tu-Wed and some did Th-Fri (I did Th-Fri).
   
3. My actual Poster was terrible. But me talking about it and pointing to things was good. This was true in general- other peoples posters were hard to understand if the person wasn't there to clarify and explain, but was pretty good if they were. And it was nice to be able to ask questions directly and interrupt, unlike talks.
   
4. As someone LISTENING to a poster talk it was better than a real talk. In one case I listened, went home that night,
   wrote some things down, realized I missed a point, and asked him again the next day.
   
5. As someone GIVING a poster talk... it was very odd. I explained my results and a simple proof of one of them about 40 times in a 2 day period. I happen to like this (note that I've taught VDWs theorem at least W(6,2) times). But even though I like it, it was tiring. You know how it is ---- the first 35 times you explain a theorem you're excited about it, but then it got to be old hat (which would have been fine if it was a talk on a hat problem).
   
6. There were 60 posters.
   

This was overall a positive experience but, again, tiring.

So would this work for STOC/FOCS or other existing conferences? We would have to adjust our mentality to thinking that posters were not less prestigious. I don't think this will happen. But what about a new conference? If some new conference in theory gets started perhaps they should look into this model. A new conference does not have to follow the STOC/FOCS model.

A(nother) nice use of Gen Functions

In a prior post I tried to give a simple example of a proof that uses Gen Functions where there was no other way to do it. For better or worse, before I posted it, my HS student Sam found a better way and I posted both proofs.

I have another example. Noga Alon showed this to be over dinner at the Erdos 100th Bday conference. (He claims that the proof he showed me is NOT his but he doesn't know whose it is. I will still call it Noga's Proof for shorthand.)

Let

A+A = { x+y : x,y ∈ A}

A+*A = { x+y : x,y ∈ A and x ≠ y }

We take both to be multisets.

Assume A is a set of natural numbers. When does A+*A determine A?

If A is of size 2 then NO, A+*A does not determine A as we could have x+y=5 but not know if A is {1,4} or {2,3}.

What if A is of size 3? Then YES:

First determine S=((x+y)+(x+z)+(y+z))/2=x+y+z.

Then determine

x = S - (y+z)

y = S - (x+z)

z = S - (x+y)

What if A has four elements? Does there exists A,B of size 4, different, such that A+*A=B+*B?

YES:

A = {1,4,12,13}

B = {2,3,11,14}

For which n does does A+*A, where A is of size n, determine A?

Selfridge and Strauss showed that this happens iff n is NOT a power of two. I have a write up Noga's proof. The original proof, in this paper, does not use gen functions and also applies to sets of complex numbers. I think Noga's proof can be modified to apply here. Which proof is better? A matter of taste; however, Noga's proof can be sketched on a greasy paper placemat in an outdoor restaurant in Budapest while the original proof cannot.

DUMP YOUR TABLES! (the moral of my story that started with a hat problem)

Recall from my last post:

PROBLEM 1: There are n people sitting on chairs in a row. Call them p1,...,pn. They will soon have HATS put on their heads, RED or BLUE. Nobody can see their own hat color. pn can see p(n-1),...,p1. More generally, pi can see all pj j < i.

Here is the game and the goal: Mr. Bad will put hats on people any way he likes (could be RBRBRB..., could be RRRBBB, could be ALL R's - like when a teacher has a T/F test where they are all FALSE.)
Then pn says R or B, p(n-1) says R or B, etc. When people say the color everyone else can hear it.
They want to MAXIMIZE how many of them say THEIR hat color. The people can meet ahead of time to discuss and agree on a strategy.
Mr. Bad knows the strategy the people will use.

What is the best they can do? Answer: n-1:

pn says RED if the number of REDS he sees is EVEN, BLUE if the number of REDS he sees is ODD. p(n-1) sees all ahead of him, knows the parity of all of them, can deduce his own hat. So can everyone ahead of him- KEY is that they use BOTH what they heard from the people who already spoke and what they see ahead of them. So can do n-1. (NOTE- a nice but not-optimal solution that some people have told me is to use the first log n people to code how many of the remaining hats are RED- this yields n- log(n) correct.)

PROBLEM 2: Same as Problem 2 but now there are c colors of hats.

That hats are colors 0,1,...,c-1. p(n) SUMS up all of the hats ahead of him MOD c. He says that number. p(n-1) heard that answer, See's whats ahead of him and sums that, and can deduce his own color. Again n-1 get it right.

OKAY, that's the problem and the answer. NOW my story and point:

I once had a group of College Students in a summer program working on PROBLEM 1. The plan was that they would first do the people-in-a-row-2-colors version, then people-in-a-row-c-colors version, then other versions. One can learn much math from looking at many variants. They began with the 2-color case and begun working out some examples. They had these tables (Note the word TABLES for later) for the n=3 case - really large decision trees- that (I think) did yield 2 people correct. They then had a table for n=4 where (I think) 2 people correct. They worked out a few more as well, perhaps getting up to n=8. The tables got larger and larger and more complicated. I never did quite understand their tables; however, they may have been doing an ad hoc version of the strategy where
n-log(n) people get the correct hats.)

I let them go on (perhaps too long) since they kept telling me NO BILL, DON"T TELL US HOW TO DO IT, IF YOU KNOW. And I was hoping they would have a breakthrough. But by the end of the second week they still hadn't gotten it (NOTE- this is not an indication that they were bad students--- its hard to tell how hard it is to see the trick once you know it) and asked me if I knew how to do it. I told them the solution above using Parity. I THOUGHT they would say OH, that's very nice, now lets see if we can do something similar for c-colors. But no. They insisted that their solution using tables was more intuitive or more informative or more ... something. None of that is remotely true. What is true is that by that point they were emotionally invested in their tables.

I kept saying DUMP YOUR TABLES now that you have a better way of doing it. They never did. But the phrase DUMP YOUR TABLES I now
use to mean DUMP SOME OLD WAY OF DOING THINGS THAT YOU ARE EMOTIONALLY ATTACHED TO BUT REALLY DOES NOT WORK.
Once you are aware of this phenomena you can see it often.

1. You have a proof that uses a certain technique that you like (in my case perhaps Ramsey Theory) but then a better proof comes along. You have to admit that the new proof is better. DUMP YOUR TABLES.
   
2. Your proof idea is beautiful but it just doesn't work. SHOULD YOU DUMP YOUR TABLES? Hard to tell- might work later.
   
3. You get emotionally attached to a certain way to teach a course. Times change, technology changes, and perhaps you should DUMP YOUR TABLES.
   
4. I have an idea for a blog entry that I think is really good and I begin writing it, and it just isn't working. I SHOULD DUMP MY TABLES.
   
5. Sometimes in a story there is ONE really good idea and the rest is crap. This might be that the author had ONE really good idea
   but could not build a good story around it. He should have DUMPED HIS TABLES.
   
6. You have a phrase that you are fond of but it distracts from the point you are trying to make. You should
   DUMP YOUR TABLES
   (See Here For a case).
   

A problem and later a story and a point.

I have (1) a math problem to tell you about (though I suspect many readers already know it), (2) a story about it, and (3) a point to make. TODAY I'll just do the math problem. Feel free to leave comment with solutions--- so if you haven't seen it before and want to try it, then don't look at the comments. Tommorow or later I will tell you the story and make my points.


PROBLEM 1: There are n people sitting on chairs in a row. Call them p1,...,pn. They will soon have HATS put on their heads, RED or BLUE. Nobody can see their own hat color. pn can see p(n-1),...,p1. More generally, pi can see all pj j < i. They CAN meet ahead of time to discuss strategy.

Here is the game and the goal: Mr. Bad will put hats on people any way he likes (could be RBRBRB..., could be RRRBBB, could be ALL R's - like when a teacher has a T/F test where they are all FALSE.) Then pn says R or B, p(n-1) says R or B, etc. They want to MAXIMIZE how many of them say THEIR hat color. Assume that Mr. Bad knows the strategy the people will use.

What is the best they can do?

Here is a strategy: pn says R if the MAJORITY are R, and B if the MAJORITY are B, and then everyone says what pn says. They are guaranteed around n/2 correct.

Here is a strategy: Assume n is even. pn says the color of p(n-1). p(n-1) then says what pn said and gets it right. then p(n-2) says what p(n-3) has. Then p(n-3) gets it right. You are guaranteed to get around n/2 right.

GEE- can we do better than n/2? Or can one prove (perhaps using Ramsey Theory, perhaps something I learned at Erdos 100 over dinner) that you can't beat n/2 (or perhaps something like n/2 + log(log(n))).

PROBLEM 2: Same as Problem 2 but now there are c colors of hats.

NOTE- there are MANY hat problems and MANY variants of this scenario--- some where you want to maximize prob of getting them all right, some where everyone sees everyones hat but their own. These are all fine problems, but I am just talking about (1) people are in a row, (2) Want to maximize how many they get right in the worst case.

ADDED LATER- WARNING- THE ANSWER TO PROBLEM 1 IS IN THE COMMENTS NOW.
SO IF YOU WANT TO SOLVE IT YOURSELF DO NOT LOOK AT THE COMMENTS.

Combinatorics use to not get any respect. But because of Erdos...

(This blog is based on things I heard at the Erdos 100th Bday Conference)

I have spend the last week at the Erdos 100th bday conference. One point that was made many times: the acceptance of Combinatorics by the mathematics community and Erdos's effect on that.

In the 1950's combinatorics was seen as recreational but not as serious math. In the 1970's you could get a PhD in it but it was still seen as suspect. Even at the time of Erdos's death (September 1996) it was still not that well regarded. Now it is, as evidenced by Szemeredi getting the Abel Prize (Gowers and Tao getting the Fields Medal is also evidence, though not as strong since one could argue that they are not really combinatorists). What changed?

1. I would have thought Szemeredi's theorem (1975) would have turned people around on combinatorics. It didn't. Roth proved the k=3 case in the 1950's, using Fourier Analysis (``Real Math'') but Szemeredi's proof of the general case was ``purely combinatorial'' and hence of less interest. Furstenberg's proof that used Ergodic theory helped put it on the mathematical map (is the Mathematical map a bijection?) but combinatorics still was not well regarded.
   
2. Erdos got many people interested in combinatorics and the connections of it to other areas such as number theory. He had incredibly good taste in problems in that the problems he suggested often lead to deep mathematics of interest, and to more problems of interest. His emphasis on asymptotics, which now seems so natural, was revolutionary at the time and later had applications to computer science. His constant pushing for better and better results, his concept of Proof from THE BOOK his encouraging epsilons and deltas to pursue mathematics, all had a profound affect on mathematics and mathematicians.
   
3. One of the reasons for the disdain was that it was seen as recreational math. This was damming for two reasons (1) the problems were not important, and (2) the proofs were easy. Both are unfair. This may have been true at one time but they became less true over time.
   
   1. Problems not important: P vs NP is certainly important. Ramsey Theory reveals hidden
      regular structure and is important. Much of the work that has gone into better bounds
      on the VDW numbers is very important and involves deep mathematics.
      
   2. Proofs are easy: People are using Fourier analysis and ergodic theory and others tools that are rather difficult. Here we have the No true Scotsman Fallacy where people claim that if it uses these tools then its not combinatorics. This raises the question of if a field is defined by its methods or by its problems. In any case, people are solving problems in combinatorics using hard methods. But even among so-called easy proofs, they often exhibit the NP-phenomena where they are easy to verify and hence LOOK easy, but are hard to come up with.
      
4. One of the reasons for the respect is computer science. Just as Continuous math was just the right tool for physics, discrete math is just the right tool for computer science. This lead to a rich source of problems for combinatorists that in turn lead to interesting techniques.
   
5. Erdos stressed asymptotics which was just the right approach for computer science.
   

How much was Erdos responsible for the respect combinatorics has now? For those who believe in The Great Person theory of history, one person CAN make a difference and perhaps Erdos is one of those people. Would combinatorics have moved into the mainstream without Erdos? I think combinatorics would have gotten respect in year n where n might be large. With Erdos, n is smaller. Perhaps much smaller. I leave it to the reader to work out the proper asymptotics.

AltaVista versus Google

Today Yahoo is closing AltaVista, the best search engine before Google. The news caught me by surprise, AltaVista still existed? A number of commentators attribute bad management for AltaVista losing its dominance to Google. But it was an algorithm that killed the search engine.

AltaVista made its claim to fame in the mid-90's by indexing a large number of web pages. AltaVista did very well for obscure search terms like "fortnow" but didn't do so well for more common searches. I used to run a test on search engines by looking for "Holiday Inn", a popular hotel chain in the US. When you search AltaVista for Holiday Inn, the first thing listed was a Holiday Inn in Buffalo, New York. The Holiday Inn home page was nowhere to be found on the search results.

For searches like Holiday Inn, one had to use Yahoo, which back then was not a search engine but a directory tree of web sites. We needed our own directories as well. Ian Parberry maintained the TCS Virtual Rolodex, a list of home pages of theoretical computer scientists, most of which had names common enough that AltaVista wouldn't find them.

A Stanford professor (I can't remember which one) came to give a talk at the University of Chicago around 1997 and he mentioned a research project at Stanford developing a new search engine known as Google. I tested Google with my Holiday Inn test and was in shock when the Holiday Inn home page showed up as the first time. Google passed every other test I could throw at it and I've rarely used any other search engine since. Google made AltaVista, the Yahoo directory and the TCS rolodex irrelevant. Google's PageRank algorithm simply took search to a new level, like the way that Steve Jobs didn't create the first smart phone but completely changed the game with the iPhone. AltaVista managed to survive for another 15+ years but never recovered market share.

The AltaVista story leads to a lesson we still tackle today. Collecting and storing big data is a huge technical challenge but data by itself is of limited value without the algorithms to find the important parts among the muck.

Computability in Europe

Bill and I are both in Europe this week. I'm in Milan at Computability in Europe and Bill is 500 miles away in Budapest for the Paul Erdős Centenary. The US 4th of July holiday doesn't seem to sway the the Europeans from holding workshops. Bill will report on the star-studded Erdős celebration when he gets back.

So what is "Computability in Europe"? Don't the Europeans use the same Turing machines that we do? Wasn't Turing European?

Or course computation is the same, whether we do it in the US or Europe, Japan or Jupiter, but the emphasis is different. In the US we typically deal with traditional models of computers and see how much time and memory we need to solve various problems. The theme of this year's CiE is "The Nature of Computing" with "nature" being the key word. The conference is co-located with the Unconventional Computation and Natural Computation conference that focuses on different models of computing, especially those that rise from nature like biological computing. The two tutorials this week come from Grzegorz Rozenberg, talking on computing modes based on living cells and Gilles Brassard (whom I didn't recognize without his trademark beard) on quantum models.

Me, I like my computation served straight up on Turing machines, thank you very much.

Friends Don't Let Friends Carpool

The AAA foundation measured cognitive distraction while driving and reported that having a passenger in the car is as dangerous as using a cell phone. On a scale of 1 to 5, a handheld cell phone caused a distraction level of 2.45, a passenger 2.33 and a hands-free phone 2.27. On top of this, distraction causes risk to a passenger as well as a driver, whereas the other side of the cell phone conversation can't be harmed by a driver's distraction.

Since the popular media ignores this risk, as a public service I present some guidelines:

1. Avoid carpooling whenever possible. While there are some advantages (less traffic, pollution and loss of natural resources), it is worth putting lives of the driver, passengers and others at extra risk?
2. If you do carpool, do not talk to each other except in case of emergency.
3. If you need to talk, pull over to a safe place and turn off your engine before engaging in conversation.

Car manufacturers must share some of the blame by building cars with multiple seats and not physically separating the driver from the other passengers.

In the same study, the AAA foundation rated solving difficult math and verbal tasks at the top distraction level of 5. So some words of advice particularly for readers of this blog

Don't Drive and Derive

Quantum Tecniques/Gen Functions- don't be afraid of new techniques

Ronald de Wolf gave a GREAT talk at CCC on the uses of Quantum techniques to Classical Problems. He made the analogy of using the Prob Method to prove non-prob results. This reminded me of the following false counterarguments I've heard about new techniques:

1. The Prob Method: Isn't that just counting?
   
2. Kolg complexity: Isn't that just the Prob Method?
   
3. Information complexity: Isn't that just Kolg complexity?
   
4. Counting: Isn't that just Information Complexity?
   

In all of the cases above the complaint is idiotic--- while one COULD translate some (all?) proofs using Prob Method to Counting, it is easier to think in terms of Prob. The translation would be harder than just getting used to thinking probabilistically. By coincidence I spend some of my time at CCC looking for simple examples of generating functions where it would be difficult to do it any other way. I found one and liked it so much that I did a write up FOR YOU MY READERS! I suspect that it COULD be done using just algebra (or something) but you wouldn't want to. Here is the theorem and a link to my write up:

(Schur's Theorem) Let a₁,a₂,...,a_L be denominations of coins such that no number ≥ 2 divides all of them. Then, for large n, the number of ways to make change of n cents is

n^L-1/((L-1)! a₁ a₂ ... a_L) + O(n^L-2)

For full proof see here. My writeup is based on that in Wilf's book generatingfunctionology (the title page really does use a small g for the first letter).


The above was my INTENDED POST. However, when I showed the Gen-function proof of Schur's theorem to some students, one of them, Sam (a HS student), came back the next day with a purely combinatorial proof. It was not completely rigorous but I am sure that he and most of my readers, could make it so without too much effort. While having two proofs (Gen-function and Combinatorial) is MORE enlightening for me and for my readers, it does dampen my point that this is a theorem for which the gen-function proof is easier. I COULD argue that the gen-function proof did not require as much cleverness, or that once you put in the rigor it is harder, but I don't really have confidence in those arguments. I include the combinatorial proof in the writeup pointed to above. Which proof is better? A matter of taste. However, I hope you enjoy both of them!

Automate Me

An economist friend asked me if there were still productivity gains to be had for office workers (like us). After all, we have email, social networks, skype and other easy ways to connect with everyone not to mention search for everything. Most tasks are pretty straightforward to do online. How much easier can it get?

There are some obvious answers to his question, such as better automated filtering of all the information thrown at us. But here's what I really would love to see--an automated electronic me.

I have about 115000 email conversations in Gmail not counting spam. Google must have tens or hundreds of billions of emails from everyone combined.

So Google can learn both how many emails are typically answered and also my particular email style. So when I hit reply, Gmail should be able to pre-fill a reasonable reply. I can edit as needed and then send. Saves me much time.

Of course Google will learn from the changes I make and get more accurate each time. After a while I can trust Gmail just to answer a subset of my email. After a while it can answer most of my email. In the future Google can referee papers, write my blog posts and prepare my class lectures.

I can hide out and proof theorems while Google does everything else for me. Until Google proves its own theorems and then I'm just out of a job.

Fraud or not ?

For each of these, are they frauds?

1. The Turk was a chess playing ``computer'' (around 1770) that was later discovered to be cheating--- a human made the moves. As Ken Regan knows well, we now have the opposite problem- humans who cheat by having a computer make the moves. Note that the Turk still played an excellent game of chess and hid the human element. This IS an achievement--- just not the one people wanted. Fraud? Yes
   
2. I once heard a rumor (NOTE- this may not be true, that's why its called a rumor) that Hybrid cars get good gas mileage NOT because of the battery but because in their effort to get good mileage they rethought other things like the aerodynamics and how the gas powers the car. If I buy a hybrid car that gets 45 miles and hour but then find out that it gets this NOT because of the battery, but because of really really good enginnering- was I cheated? My sense is NO since I wanted good gas mileage. I may wonder why I need to replace the battery, or even if I need to. Fraud: I'll say NO but its certainly debatable.
   
3. Someone sells a single-purpose quantum computer to factor numbers and it works REALLY WELL but later it is discovered that it didn't use quantum at all(!)---it instead used a new classical algorithms (e.g., an extension of the Number field Sieve)--- would the buyers consider themselves cheated?
   
   1. If the buyers were people who just want to factor really large numbers then perhaps they wouldn't care.
      
   2. If the device was meant to fool granting agencies or venture capatilists to fund more quantum, then it is fraud. One may wonder why the device-maker didn't just apply for funding in crypto.
      
   3. If the buyer is an academic who then writes an article about how quantum computing is finally practical, when the truth is discovered he may have his credibility (unfairly?) tarnished.
      
4. What if someone had a quantum computer that factored really well but was advertised as a really good classical algorithm that used hard number theory? Somehow that seems very funny to me as a scenario so I won't even ponder fraud or not.
   
5. I have heard that the current quantum computers that do such miraculous things as factor 15 (darling says `factor 15? I could do that without breaking a sweat') or find R(3) (I always thought it was 6 and now I know!) may not be ``really quantum'' . This is problematic since nobody really wants to factor 15 or find R(3)--- that is, there is no analog to the people who want good gas mileage or the people who want to factor large numbers in my two examples above. These devices are JUST for demonstration purposes. If its not quantum, its not demonstrating anything. Fraud? Yes, but are they really fooling anyone?
   

The Internship

Last weekend I took my teenage daughters to see The Internship, the Vince Vaughn-Owen Wilson vehicle where they play two forty-year old interns at Google. It basically follows the standard underdog story Vince Vaughn so greatly spoofed in Dodgeball.

We went since most of the Google scenes were filmed at Georgia Tech last summer, with the climatic final meeting filmed in the atrium of the Klaus building that houses the School of Computer Science.

The movie was at best mildly amusing and not too often do you see an Emacs vs Vi discussion in a major motion picture. Mostly the movie played as an homage to Google, what a wonderful magical place it is and all the great things they do for the world. To some extent that worked: Both of my daughters came out of the movie wanting to work at Google.

Larry Page, talking about the movie said "The reason we got involved with the movie ‘The Internship’ is that computer science has a marketing problem. We're the nerdy curmudgeons." I do think CS has a marketing problem, though recently of a very different nature.

The US government is using big data as big brother. The US-China discussions on cyber attacks remind me of the US-USSR talks on nuclear weapons in the 70's. Let's not mention how some people believe computers are destroying jobs and widening the gap between the haves and have-nots.

But of course I remain very bullish on computer science and the great things we can achieve with computing. And sometimes it takes silly movies like The Internship to drive that point home.

STOC: Some NON-radical ideas

At the STOC business meeting Joan Feigenbaum (PC chair) raised some very good points. There was no real discussion (or perhaps the burning car was the discussion). Here are the issues and some thoughts as I see them. Note that I am not speaking in any official capacity. I speak of STOC but many of my comments apply to other conferences.


What is the purpose of STOC? Initially it was to help spread knowledge of the latest results, through both talks and lunch. Even though we can now tweet the latest VDW numbers, STOC still serves this purpose. Another (likely unintended) purpose of STOC is to give researchers a quick yet prestigious way to publish. Hiring committees and Tenure committee's DO ask questions like How many STOC/FOCS publications does she have?. Some people think this is an awful system since these papers are not refereed carefully. I am not going to debate that here. My only concern is making STOC better at spreading knowledge.

What are some of the problems with STOC?

1. People don't want to serve on the program committee since its a lot of time and they can't submit. The two-tiered system used for STOC 2013 seems like a good solution to this.
   
2. Referees Reports (can we even call them that?) are often not very informative. The two-tiered system COULD help this since each committee member has less work and there is a small oversight committee. Another solution that some conferences use is to give the authors a chance to rebut a report and/or rewrite the paper. I'll discuss this more in the next point.
   
3. Since the reviewing process is rushed there have been papers that are just plain WRONG. This can be confusing for someone coming to the literature. Also there are throw-away- comments like This can easily be extended to the case of weighted graphs. where this is not easy at all. How big a problem is this? How much worse than Journals is it? I DON"T KNOW. Would the Rebut/Rewrite help this? PRO: Referees don't have to decide RIGHT NOW what to do and can ask the authors things? CON: More back and fourth, more work. CAVEAT: This might make STOC more like a journal with fast turn-around time.
   
4. Some of the papers never get into Journal Form. Again Rebut/Rewrite may help in that the STOC version is better, but this is more giving in to the problem rather than solving it. Demanding full versions of papers (now possible since with e-proceedings page limits are less of an issue) is a good idea (and I think IS being used now by STOC).
   
5. Many good papers get turned down. Going to three parallel sessions would help this. There may be logistical problems here, but I think this is a good idea. Are there enough good papers to make this work? I think so- and the committee would have the freedom to NOT use all the sessions in case there aren't quite enough papers. I do not think this would make STOC's prestige decline.
   
6. It has been said that only narrow technically hard stuff gets in and not simple short new ideas. Its hard to know if this is really true. But in any case the three-parallel sessions may help this since there would be room for diff types of papers.
   
7. Personally I get more out of the workshops and invited talks then out of the refereed talks. Hence I would like more of those. Posters are good also. More to the point- I would like more VARIETY in whats at a conference since people get knowledge in different ways.
   
8. Can you really communicate your latest and greatest result in a 20 minute time slot in a crowded room where the adjacent bathroom is out of order? Even though we've made great advances in technology (I call PowerPoint PROGRESS but some disagree) and in plumbing (in the old days STOC people had to use an outhouse- do young people even know what an outhouse is anymore?), is there a better way to do this? It was suggested that ALL talks be POSTER sessions (NIPS does this). This should NOT be viewed as inferior or demeaning so long as we still have published proceedings (whatever that means in the days of arXiv) and high standards. The only relevant question is: Would posters be a better way to convey results? I DO NOT KNOW, but I think it would be worth trying out.
   

So in summary I want to see (1) more workshops, invited talks, and student posters, (2) Full papers in the proceedings, (3) two-tiered program comm. (4) either go to three parallel sessions or have posters. Some of these could be combined-- like a workshop on max flows, and them posters on the max flow papers that got in. The rebut/rewrite I am more ambivalent on but that may also be a good idea. These ideas are NOT radical (and not even original) and it is NOT my purpose to drain STOC of its prestige. Whether that is a good idea is another debate.

Complexity Typecast

Lance: Welcome to another exciting typecast coming from sunny Stanford University. I'm with Bill at the 28th Conference on Computational Complexity. Hi Bill, I see you're now at Mizzou.

Bill: Yes, my name tag says Univ. of Missouri but the body is still at Maryland. But Missouri is the Show-Me State and I don't believe theorems until you show me the proof.

Lance: Interesting name tags going around. Joshua Brody is at the University of Aarhus in Windsor, Vermont. But outside the name tags, this has been a well-run meeting.

Bill: Indeed. So Lance, anything seem different this year.

Lance: I'm noticing a few trends at both STOC and Complexity. Both have strong attendance this year, especially for West Coast meetings, and more papers than usual. Though fewer women attendees and I'm not sure why.

Bill: I was at a computability meeting at Iowa recently where there six women but they were the same six women from twenty years ago. That does not bode for the future.

Lance: I think that says more about computability as I'm guessing all the attendees were there twenty years ago.

Bill: I resemble that remark. Let's talk math. At one you were a Kolmogorov skeptic, now you are a believer.

Lance: Yes once I actually used it for a theorem I saw the light.

Bill: Speaking of light, are you now a quantum believer? Ronald de Wolf gave an awesome talk on the applications of quantum techniques to classical theorems. Were you convinced?

Lance: There are times that thinking quantumly can help generate good theorems. Nice to see quantum is good for something.

Bill: They didn't have quantum back in the days of the first complexity conference in 1986.

Lance: Yes the world was classical back then, just like the world was flat in 1400. No one here remembers that complexity meeting in 1400 but I have seen a few people from the original 1986 meeting.

Bill: Besides us, Eric Allender, Jonathan Buss, Steve Homer and Osamu Watanabe. Whether we remember anything from those days...

Lance: I remember meeting you for the first time. I was just a first-year grad student and I walked into a room with you and David Barrington talking at light speed. I thought you were both so smart.

Bill: Sorry to disappoint you. So Eric is the last man standing?

Lance: Yes, since I missed complexity last year, Eric Allender is the only person to have attended all 28 Complexity meetings. He does not want that to be his claim to fame.

Bill: Back in '86 I could follow 2/3 of 3/4 of the talks. Now I can follow 1/8 of 1/4 of all the talk. Have I gotten dumber or have the talks gotten harder?

Lance: Yes.

Bill: Thank you Lance, how about you?

Lance: Yes. More the techniques are quite different than the more computability type tools we used back in the day.

Bill: A field must change or die. I'm glad we're changing unlike certain areas of math I will not mention.

Lance: Speaking of change...

Bill: There are 242 ways of changing a dollar into pennies, nickels, dimes and quarters.

Lance: I did not know that! Moving on, what do you think of Joan Feigenbaum's suggestions on changing STOC?

Bill: I'll do a blog post on this later, but I'm generally in favor of more people on the PC (2-tiered), more papers in conference (3 parallel sessions) and more workshops, invited papers and posters.

Lance: So Bill ready to wrap it up?

Bill: Yes, it's time.

Lance: So remember, in a complex world best to keep it simple. And buy my book.

STOC is Burning

Bill and I are in Palo Alto this week for the co-located meetings of STOC and Complexity. In a new ACM policy, the STOC 2013 papers are freely downloadable by all for the next month. Check out the best papers and best student papers.

Last night smoke from a burning car preemptively ended the STOC business meeting.

Photo from Moritz Hardt

Before the fire I live tweeted the business meeting. In short, a possible record attendance for a west coast meeting (364), one less than New York last year. Next year's STOC will be in the same hotel in New York. A record number of accepted papes (100). PC chair Joan Feigenbaum talked about her two-tiered committee and several potential experiments for future STOCs (eliminate proceedings and just point to Arxiv papers for instance). Read her blog interview for more. 

Lane Hemaspaandra received the SIGACT distinguished service prize for running the SIGACT News complexity column. Gautam Kamath won the STOC 2012 best student presentation award. No award this year because there aren't videos for the talks.

Gary Miller gave the Knuth Prize lecture. He talked about new techniques for solving systems of equations based on graphs that has many applications including new almost linear time algorithms for approximating undirected max flow. 

More from Palo Alto later this week. 

The High Quality Research Act

Lots of talk, mostly negative, about the proposed High Quality Research Act.

Prior to making an award of any contract or grant funding for a scientific research project, the Director of the National Science Foundation shall publish a statement on the public website of the Foundation that certifies that the research project
(1) is in the interests of the United States to advance the national health, prosperity, or welfare, and to secure the national defense by promoting the progress of science;
(2) is the finest quality, is groundbreaking, and answers questions or solves problems that are of  utmost importance to society at large; and
(3) is not duplicative of other research projects being funded by the Foundation or other Federal science agencies.

On the whole, doesn't sound like a bad thing. So why the fuss? Because the bill's sponsor Lamar Smith, republican congressman from Texas and chair of the house science committee, also sent a letter to the NSF acting director asking for the reviews on five grant proposals. So the High Quality Research Act is an attempt to give congressional approval to the grants process and perhaps requiring justification of individual grants. Nothing good can come from that.

The NSF bravely said no to Smith's request for the reviews. That was two weeks ago and I haven't seen any new news on the topic. Let's hope that High Quality Research Act just simply disappears.

Theory Jobs 2013

Time for the annual spring jobs posts. Like last year, I set up a Google Spreadsheet that everyone can edit so we can crowd source who is going where next year.

A reminder of the rules

• I set up separate sheets for faculty, industry, postdoc/visitors and students.
• People should be connected to theoretical computer science, broadly defined.
• Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
• You are welcome to add yourself, or people your department has hired.

This document will continue to grow as more jobs settle. So check it often.



Edit

Quantum Computing Fast and Slow

I just read two very different science books, Daniel Kahneman's Thinking, Fast and Slow and Scott Aaronson's Quantum Computing since Democritus. Not much to connect the two except both deal to some extent about probability and computation and I want to write a blog post for each chapter, for much I disagree with both authors. But that's what makes them so much fun, so rare to find science-oriented books both worth reading that have the guts to say things that one can disagree with.

In full disclosure, Scott and I agree that he would post about my book if I wrote about his but what a deal. Scott's book is a pleasure to read. He weaves the story of logic, computation and quantum computing into a wonderful tour. You can get an idea of Scott's style by how he explains how he will explain quantum.

The second way to teach quantum mechanics eschews a blow-by-blow account of its discovery, and instead starts directly from the conceptual core - namely, a certain generalization of the laws of probability to allow minu signs (and more generally, complex numbers). Once you understand that core, you can then sprinkle in physics to taste, and calculate the spectrum of whatever atom you want.

He approaches the whole book by this philosophy.  Every now and then he moves into technical details that are best skipped--either you already know it or will get lost trying to follow. But no problem, the story remains. You need to appreciate Scott's sense of humor and his philosophical tendencies, and he does get way too philosophical near the end, particularly a strange attack on Bayesian that involves God flipping a coin. At the end of the book Scott contemplates whether computer science should have been part of a physics department but after one reads this book the real question is whether physics should be part of a CS department.

Kahneman gives a readable tour of behavioral economics with a variety of examples, though I don't agree with his interpretation of many of them. His fast and slow refers to decisions we make instinctively and quickly (like judging a person based on first impressions) versus more slow and deliberative (like multiplying numbers). There is a computer science analogy, in that his fast refers to what we can do with machine learning, simple trained models to make quick judgments that occasionally gets things wrong. I'm not a huge fan of behavioral economics, but it is useful in life to know the probability mistakes people make so you can avoid making them yourself. The wikipedia article has a nice summary of the effects mentioned in the book.

While these two books cover completely different areas, the themes of probability and computation pervade both of them. One simply cannot truly understand physics, economics, psychology and for that matter biology unless one realizes the computational underpinnings of all of them.

Do you KNOW how you KNOW what you KNOW? I don't KNOW.

When watching Jeopardy with Darling if I get a question correct that is NOT in my usual store of knowledge (that is NOT Ramsey Theory, NOT Vice Presidents, NOT Satires of Bob Dylan) Darling asks me How did you know that? I usually reply I do not know how I knew that. Recently I DID know and I'll get to that later, but for now the question arises: Do you know how you know what you know?

1. As an undergrad I learned mostly from taking courses. Hence I could say things like I Know Group theory from a course I had in Abstract Algebra in the Fall of 1978 (Side Note- I know why I should care about groups from reading the algorithm for graph isom for graphs of bounded degree---in 1988). I learned a few things on my own- I learned that a graph is Eulerian iff every vertex has even degree from a Martin Gardner article. But since most of my knowledge was from courses I knew how I knew what I knew.
   
2. As a grad students I still took courses but more routes to knowledge emerged. Papers! I could say things like
   I know the oracle constructions about P vs NP because I read the Baker Gill Solovay paper on October 23, 1981. It helps that Oct 23 is Weird Al's birthday. But even here things get a bit murky- someone TOLD ME about the paper which lead me to read it, but I don't recall who. So one more route to knowledge emerged- people telling you stuff in the hallways.
   
3. I saw Anil Nerode give a talk on Recursive Mathematics and that day went to the library (ask your grandmother what a library is) and read some articles on it. This was well timed- I knew enough recursion theory and combinatorics to read up on recursive combinatorics. In this case I know exactly how I know what I know. Might be the last time.
   
4. As a professor I read papers, hear talks, hear things in hallways, and learn stuff. Its getting harder to know how I know things, but to some extend I still could. Until...
   
5. THE WEB. The Web is the main reason I don't know how I know things. I sometimes tell Darling I read it on the web which is (a) prob true, and (b) prob not very insightful.
   

So- do you know how you know what you know?

On Jeopardy recently the final Jeopardy question was as follows.

TOPIC: Island Countries.

ANSWER: No longer Western, this one-word nation has moved to the west side of the international Date Line to join Asia and Australia.

BILL: What is SAMOA!?

Darling wondered how I know that:

DARLING: How did you know that? Is there a Ramsey Theorist in Samoa?

BILL: Not that I know if, but that's a good guess as to how I knew that. Actually Lance had a blog post Those Happy Samoans about Samoa going over the international dateline and losing the advantage of having more time to work on their conference submissions.

DARLING: Too bad there isn't a Ramsey Theorist there to take advantage of that!

Thanks Lance!- In this one case I know how I know what I know!

The MOOCs Degree

Earlier this week Georgia Tech announced the Online Masters of Science in Computer Science, a MOOCs-based degree with a total tuition of about $7000. This degree came out of a collaboration between Sebastian Thrun of Udacity and my dean Zvi Galil with some significant financial support from AT&T. We've spent several months getting faculty input and buy-in to the program and we're very excited about taking a new leading role in the MOOCs revolution.

We will roll out slowly, with a smaller scale courses to corporate affiliates to work out the kinks and the plan to go to the general public in fall 2014. Read the FAQ to get more information about the program.

It's been fun watching the development of this degree, in particular hearing Sebastian talk about his MOOC 2.0 plans to scale courses with a small amount of expense that we pull from the tuition. No doubt we will have challenges in making this degree truly work at a large scale but I'm truly bullish that we'll a self-sustaining quality Masters program that will reach tens if not hundreds of thousands of students.

Here we go.

Mother's Day Math

Problem: On Mothers day (May 12 this year) restaurants are very crowded because many people take their mothers, grandmothers, great-grandmothers, etc out to lunch. (Grandparents day is in September but I think most people ignore that and honor their grandmothers on mothers day and their grandfathers on fathers day.)

My solution: Take mom out to lunch the FOLLOWING week. Some of my friends tell me NO- you can't just MOVE Mothers day- what are you--- The Master of Space and Time? The key is that my mom AGREES with me and in fact raised me with these values: (1) Never do X when everyone else is doing X, its too crowed, and (2) Learn the polynomial VDW theorem.

While this solution may work for me, it may not work for everyone. Here are some options to alleviate the restaurant crunch:

1. Declare the second WEEKEND in May to be MOTHERS WEEKEND. People take their moms out to lunch SATURDAY or SUNDAY. This would split the restaurant load in half.
   
2. Declare May MOTHERS MONTH. People take their moms out to lunch ONE Sunday in May. This would split the restaurant load by 4.
   
3. Declare May MOTHERS MONTH. People take their moms out to lunch ONE Saturday OR Sunday in May. This would split the restaurant load by 8.
   
4. Declare May MOTHERS MONTH. People take their moms out to breakfast OR lunch OR Dinner ONE Saturday OR Sunday in May. This would split the restaurant load by 24.

How would people DECIDE which day to do:

1. The last day of April have mom either (depending on which of the above schemes) flip a coin, role a 4-sided die, or role an 8-sided die or role two 12-sided dice to determine which day to be taken to lunch. Fortunately, due to the Dungeons-and-Dragons craze that girls got into about 40 years ago, most mothers have these dice. But in case she does not, here is a nice MATH PROBLEM (I am sure already solved): USE fair coins and fair 6-sided dice to simulate other random choices fairly. In our case 4-sided, 8-sided, and 24-sided. Which random choice can be simulated? Which can't?
   
2. Say we do the Saturday/Sunday/breakfast/lunch/dinner solution. Everyone with last name beginning with A goes to breakfast on the first Saturday. Everyone with last name beginning with B goes to lunch on the first Saturday. etc. There are only 24 lunches and 26 letters, so merge P and Q, and merge Y and Z.
   

How likely is any of this to come about? It would need to evolve naturally as a social custom. It also would have to not be that hard to implement. As such the 24-meal-plan probably won't catch on. Also, if Mother's Day become Mothers one-of-24-meals-day it may lose something. Hence the 2-meal-plan solution is probably the best.

However, the entire tradition of taking mom out to lunch on mothers day may fade. The origin is that mom cooks for the family most days, so this ONE day they take her out. Nice! But more and more households share responsibilities (NOTE- I have no facts or stats to back this up but it has a certain truthiness about it) hence the notion of taking mom out to lunch may seem more and more odd over time. Then again, its still nice being taken out to lunch.

GPU Computing

Back around 1980, I used to write computer games for the Apple II. Plotting a point on the Apple II screen required dividing by 7, a lengthy process for the 6502 microprocessor. Asking around, we learned how to make division by 7 much faster--lookup tables.

As computer gaming got more intense in the decades that followed, we first had graphics cards designed to speed up the process and later Graphics Processing Units or GPUs, dedicated processors devoted to graphics.

Around the turn of the century, people started using GPUs for more than just graphics. GPUs did certain kinds of vector manipulation quickly and one could use these for a variety of mostly scientific computing. But GPUs weren't really well designed for other purposes. Following the cupholder principle, GPUs began to evolve to allow easier to access APIs from more common programming languages becoming General Purpose GPU or GPGPUs. Several systems researchers at Georgia Tech and elsewhere are now redesigning chip layouts to make the best most efficient uses of CPUs and GPGPUs.

The theory community hasn't seem to catch on yet. There should be some nice theoretical model that captures the vector and other operations of a GPGPU and then we should search for algorithms that make the best use of the hardware. The theory world writes algorithms for non-existent quantum computers but not for the machines that we currently use.

Are you smarter than a fifth grader? I'm not.

My darling sometimes watches TV in the middle of the night when she can't sleep.So I found myself watching (actually listening) to the quiz show
Are You Smarter than a Fifth Grader? They asked the following Math Question:

What number do you need to add to 3 to get a double fact?

I had never heard the term double fact! I really didn't know and there was no way toderive it! I don't recall what my guess was but it was incorrect.See herefor what they are.

Is this a common term? If you Google

"Double fact" math

You get roughly 6,000 hits. (Down from 17,000 a few months ago when I first sketched out this post.)Is that enough hits to be a real term? Is number-of-hits a good measure?

Are there other math terms that are being taught in elementaryschool that are not that well known to people like us? (Though if you have children perhaps you know them.)Note that no matter how much math you know, there may be terms you don't know and can't derive (though you can make an intelligent guess).

My name is Bill Gasarch, and I am NOT smarter than a fifth grader.

Map Coloring Revisited

Following the coloring theme from Bill's last post, a few years ago I asked you readers for natural examples of maps that were and were not three colorable. Chris Bogart gave a nice non-trivial example of a three-colorable country, Armenia.

But I also wanted a natural example that was four-colorable even though every interior region had an even number of neighbors. In my book I ended up making up my own fake country map.

(Sorry for the hand-drawn picture and getting East-West wrong. Looks better in the book)

So once again I'd still like to see a natural example. Here's a simple 7-node graph with every interior node with even degree but not 3-colorable. 

There must be some real world map that captures this graph.

I'll make the same deal I made before, an autographed copy of my book for the best example of a real-world example of a non-three colorable map with interior regions with an even number of neighbors. Should be a real political unit--not just a collection of states. 

Computer Assisted Proofs- still controversial?

Kenneth Appel, of Appel-Haken Four Color Theorem Fame, died recently. See here for an obit.

In 1972 I read that the four-color theorem was an open problem. From what I read it seemed like there was some progress on it (e.g., results like `if its false the graph has to be yah-big) but it seemed to be years away from being solved. I assumed that a new idea was needed to solve it.

Then, in 1976, it was SOLVED by Appel-Haken. From what I read it wasn't so much a new idea but very clever use of old ideas and a computer program. I also heard that it was just at the brink of what computers could do at the time, and that it would have taken 1200 grad student hours. (There is a good description of the proof on Wikipedia here.)

At the time I heard there were objections to the proof. Later when I read some of them they didn't seem like real objections. They boiled down to either

1. I wish there was a shorter proof. This is true, but not a reason to object.
   
2. It can't be hand checked. I trust a computer-checker MORE THAN a human checker
   
3. We don't know WHY its true. This is a more reasonable objection- but we do know how they got it down to a finite number of cases, so I'm happy with that.
   

In 1996 Robertson, Sanders, Seymour, Thomas was obtained a simpler proof. In 2005 Werner and Gontheir formalized the proof inside Coq- a proof assistant. To quote Wikipedia This removed the need to trust the various computer programs used to verify particular cases;it is only necessary to trust the Coq Kernel At this point I doubt anyone seriously doubts that the theorem has been proven.

There have been more computer-assisted proofs since then. See here for a list of some of them. That article also claims that such proofs are controversial and not always accepted. Is this really true? I thought the controversy was gone except for the topic of the next paragraph.

A famous computer assisted proof (or perhaps ``proof'') is the Kepler Conjecture. In 1998 Thomas Hale claims to have proven it. The proof involved rather complex computer calculations. The referees say they are 99% sure its true. Here's hoping an easier proof is found.

Computer assisted proofs may become more common. I just hope we still know WHY things are true.

Was Appel-Haken the first use of computer assisted proofs? I doubt it, but it was likely the first one to have an impact. It was important to know that this kind of proof could be done.

Is there a much shorter proof? A combinatorist once told me that since the function

f(n) = max size of proofs of statements of length n

grows faster than any computable functions, there have to be some statements that have very long proofs; and perhaps the four color theorem is one of them.

Ideas in Search of a Blog Post

I keep a list of ideas for blog posts, but some will never turn into posts. So here are a few random thoughts from that list.

• Some people like to write prose, some people like to write lists, like Bill's last post. Bill will often send me an email that's a list of items. I prefer the prose and usually avoid the lists with today being the "exception that proves the rule" (an expression that I never understood).
  
  I do have to admit that lists are very efficient, when I can respond to Bill like 
1. yes
2. no
3. Friday
4. Did you really expect happy comments on that post?
• Marissa Mayer has banned working at home for Yahoo employees. Lots of academics work at home when they aren't teaching. I didn't have any more deep insights here so it didn't become a post.
• I have a note to write a blog post on "confusing university names". I wonder what was confusing me.

I'll end this post of uninteresting post ideas with the wine tasting story. At Cornell there was a popular course on wine tasting open only to graduating seniors. Alas it conflicted with graduate complexity which I took from the great Juris Hartmanis. I don't regret that choice but missed the wine.

When I was a grad student at MIT there was a wine tasting course held during the short IAP session during winter break. So we took that course. A fun course. On the last day we all dressed up for the really fine wine. The instructor came to class in his tux even though he was quite ill that day. Two days later everyone in the class got sick as well.

There ought to be a moral to that story but I haven't figured it out yet. 

Oh, I remember/recorded/DVRed it well

You can now wear a device, Memoto that will take a picture every 30 seconds. Do you really have a Kodak Moment every 30 seconds? No, but this way when you do have one it will be captured (unless it happens at just the wrong time.) There is another one called Autographer which claims to be a "smart" camera that will take tons of pictures of your day. A photographer wore one and had his team all wearing them during a photo shoot.

Current historians who study ancient civilizations have the problem of very little being preserved. They go on whatever, perhaps by chance, happened to survive. King Tut is studied NOT because he was an important king, but because we have LOTS of his stuff. (What if America is destroyed and all that is left is the Gerald Ford Library?}

Future Historians may have the problem of having too much written down, recorded, emailed, blogged, tweeted. Or they may have the problem current historians have if some of these technologies go out-of-date so a lot is lost. Floppy's are already unreadable, Video Tapes and VCR's are degrading, beta-tapes--- as your grandparents what they were. They may also have the Galaxy Quest problem of mistaking our TV shows for historical documents (oh that poor Gilligan!).

What do we and don't we preserve?

1. Almost every TV show and Movie produced since DVDs came out, no matter how bad, is on DVD. Is there a directors cuts of Dude, where's my car?? Will future generations need that?
   
2. News shows are not preserved. Too bad- I might want a complete set of THE DAILY SHOW and THE COLBERT REPORT. Future historians may have the problem of mistaking these shows for satire.
   
3. Quiz shows are not preserved. Too bad- I liked BEAT THE GEEKS but all I have are some video tapes I recorded when it was on.
   
4. Sporting events- This is borderline since there are DVDs of past Superbowl's, World Series, etc, but not of ordinary games.
   
5. Many TV movies don't make it to DVD. Is that a loss?
   
6. Much TV from before the video tape age is lost. Some survives. It is somewhat arbitrary. I Love Lucy was done on some sort of medium that survived, others did not.
   
7. A very odd case: Dr. Who. There are rumors that some fans audiotaped the early episodes and that the only form in which they are preserved. See here, here.
   
8. Commercials. Aside from arbitrary things people happen to have taped, most commercials will not survive! What will future generations do without all of those insurance companies claiming that they are cheaper than the other ones?
   
9. What if the only knowledge of complexity theory that survives is Lance's book. That would be okay!
   
10. What if the only knowledge of complexity theory that survives are the Bill/Lance Podcasts. Hmm...
    

Quasi related to the theme of today's post (today's post has a theme?) is the question Who was the first married sitcom couple to be shown sleeping in the same bed? The funny answers are The Flintstones and The Munsters, indicating that America was so prudish they couldn't show real humans in bed. The first real-human couple is then said to be the Brady Bunch. But actually a couple named Mary Kay and Johnny from a sitcom in 1947 are said to be the first. The networks were less prudish because the couple really was married (also, TV was SO new back then). But here is my point- The show DOES NOT EXIST ON VIDEO TAPE OR DVD OR ANY MEDIUM. So the answer is only people's memories which could be faulty. We are already losing access to some TV trivia! Incidentally, are there any happily married couples on TV anymore? (The FBI agent on White Collar comes to mine, but nobody else.) (Added later: Our knowledge of TV trivia is actually increasing! see here.


What about journal articles? Do we do the future a DISservice by publishing too much and making it harder to find stuff? Or will they have the tools to find what they want? Today we have Google Scholar and some other tools- but are we putting all of our eggs in one basket? Will all of our papers survive or only the good ones? Or is every paper a gem worthy of preserving for future generations? While I doubt this is true, you never know when someone is going to need the Canonical a-ary Ramsey Theorem to prove something in geometry.