My take on the Olympics

Thoughts about the Olympics

1. If you are rooting for your country, would you rather they get (say) 18 medals: 6 Gold, 6 Silver, 6 Bronze, or 17 medals: 10 Gold, 4 Silver, 3 Bronze?  More generally, when is (g,s,b) better than (g',s',b') Some schemes:
   
   
   
   1. The commentators and the websites seem to use g+s+b. They say things like
      American is leading the Medal Count without breaking it down.  Given that the margins-of-victory are often rather small, and all of the athletes who finish in the top 3 (often even in the top 20) are quite good, I think that just g+s+b is good.
      
   2. If you want to value gold medals more than a scheme like 3a+2b+c makes sense.  One problem- the weights 3,2,1 are arbitrary. What would a criteria be for good weights?
      
   3. It may be a complicated function. For example (g,s,b) is better than (g',s',b') if g ≥ g'+4 OR (g ≥ g'-3 AND g+s+b ≥ g'+s'+b').
      
   4. You may want to allow for a partial order--- that is, some triples are incomparable.
   
   
2. Swimming or running: Often the top X people are 0.5 seconds apart and all close to or better than the world or Olympic record.  I would give them all medals. This is not some wimpy self-esteem crap--- if the athletes are that close together, and close to breaking records, they really are all excellent and you really can't say whose better. A possible scheme:
   
   
   
   1. If you tie or beat a world record you get a Gold Medal. (Might even allow if you are within X of a world record for some X.)
      
   2. If nobody has beaten or tied a world record and you tie or beat an Olympic record then you get a Gold Medal.  If someone else has beaten or tied a world record then you get a Silver Medal.  (I may allow some leeway in both cases.)
      
   3. The top person behind all of those people gets the bronze Medal.
   
   
3. Or we could give more medals: Gold, Silver, Bronze, Zinc, Aluminum, maybe more.
   
4. In Women's Gymnastics these women do spectacular things but if they land badly TAKE OFF X POINTS! Somehow that doesn't seem right.
   
5. In most events Women and Men compete separately.
   
   
   
   1. Track and Swimming: Since these are timed we can say without apology that the men are better, so its best if they don't compete head-to-head. However, if a women wanted to compete in the men's event she should be allowed to (Are they now? I doubt it.) I don't think this has come up. 
   2. Gymnastics. Here its NOT that either gender is better, its just that they do different things.  The very thought of a guy on the uneven parallel bars terrifies me.  The thought of anyone doing backflips on a 4-inch wide beam also terrifies me.
      
   3. Equestrian- from what I could tell from the Yahoo Schedule Website men and women compete equally here.
      
   4. Archery and Shooting are seperated by Gender. For Archery this might make sense- some strength is required.  For Shooting this makes no sense to me. I asked a guy who knows about shooting and he told me that many non-Olympic shooting sports are not seperated by gender.  So why are the Olympic Shooting contests seperated by gender? My guess is that its the same reason COLT allows PC members to submit and CCC does not: because that's how we've always done it.
   
   
6. Game theorist needed: The rules for Badminton were set up so that it was in China's interest to throw a game (see here).  In this case I think it should be fine for a team to forfeit rather than play badly on purpose. More important- the rules need changing.  The Blog Turing's invisible Hand discussed this here.
   
7. What sport do you most want to see in the Olympics? I would say Chess Boxing or Skeet Surfing. Both make more sense then the Olympic sport of Modern Pentathlon which combines pistol shooting, fencing, freestyle swimming, show jumping, and a 3 km cross country run.

MOOCs

I haven't posted in about a month. A combination of traveling, vacation, moving to Atlanta and getting started as chair. I appreciate why Michael Mitzenmacher stopped blogging as he became department head. I'll try to post once a week but no promises.

Last week I attended the CRA Snowbird meeting, a biennial meeting of CS chairs and other leaders in the field. The big topic this year: Massively Open Online Courses or MOOCs. Coursera just a couple weeks ago had their big announcement with their line-up of universities that will produce courses including Georgia Tech.

John Hennessey, president of Stanford, gave the CRA keynote address arguing that MOOCs will save universities. He puts the untenable costs of universities at personnel costs (faculty salaries) are making colleges unaffordable (not sure I fully agree). He argued that MOOCs will help teach courses more effectively. The hidden subtext: fewer professors and probably fewer universities, or as someone joked, we'll all be branch campuses of Stanford.


As pointed out by a few at the meeting there is nothing essentially computer science about MOOCs. But it's hard to ignore the CS influence: The Stanford courses that started the new MOOC era were in computer science, Coursera and Udacity are led by computer scientists, as are the MOOC centers at Stanford, MIT, Georgia Tech and many other schools. With great influence comes great responsibility so let's be sure to do it right.


About the only thing people could agree with is that the we are in the very early stage of MOOCs produced by major universities and nobody is sure where we are going. MOOCs may completely change higher education in America and around the world. Or they won't.

A natural function with very odd properties

Last time I posted some questions. Today I post the answer that I know.

1. Is there a subset of [0,1] that is uncountable and has measure 0?  YES- take the Cantor Set.  Many readers knew this.
2. Is there such a set that is natural? Some comments thought the Cantor Set was natural. I disagree, however
   this is a matter of opinion and taste.
3. Is there a function that is continuous everywhere and differential nowhere?  YES- take the Weierstrass Function.  Many readers knew this.
4. Is there such a function that is natural? Some think the Weierstrass Function is natural. I disagree because it was constructed for the sole reason to be continuous everywhere and differential nowhere.  But again, there are those who think it is natural and this is a matter of opinion.
5. Is there a function that has derivative 0 at almost every points of [0,1] even though it is strictly increasing?
   YES- take Cantor Functions,
   also known as the Devil's staircase. Some readers knew this.
6. Is there a natural such function? YES- and this was the motivation for the post. (I also didn't want to have the example I read about mentioned in the comments of the last post which is why I wanted all posts to be non-anonymous- so if I blocked one I could email the author WHY I blocked it.)

The function I will talk about came about because of a real problem having nothing to do with finding weird functions. Hence I think it is unambiguously natural.

I base my exposition on the exposition in
How to Gamble if you Must
by Kyle Siegrist. The original source is from the classic book Inequalities for Stochastic Processes: How to Gamble
if you must by Dubbins and Savage. Classic or not, unless that book is free online the future
will credit Siegrist with the result (even though Siegrist references Dubbins and Savage.)


Consider the following game: Let 0 < p < 0.5.
Let 0 ≤ x ≤ 1. We will view p as a probability and x as how
much money you start with.
You place a bet (which has to be ≤ what you have).
A coin is flipped with prob of WIN being p and of LOSS being 1-p.
If you win you double your bet. If you lose you lose your bet.
You repeat until you have 0 or you have 1.

You could play TIMIDLY: bet a fixed small amount every time.
This is analyzed. In the paper and is interesting.


You could play BOLDLY: if you have < 1/2 then bet all you have,
and if you have ≥ 1/2 then bet so that if you win you'll have 1
and can stop.


If you play BOLDLY then
what is the probability that you will end with 1?
We will fix p and let F(x) be the prob if you begin with x.
(We assume 0 ≤ x ≤ 1.)
F satisfies the following recurrence:

F(x) = pF(2x) if x ∈ [0,0.5]

F(x) = p + (1-p)F(2x-1) if x  ∈ [0.5,1].

F(0)=0, F(1)=1

This is enough to define F on all rationals between 0 and 1 (use the expansion in base 2).
Then use continuity to define F on all the rationals between 0 and 1.

The paper claims that F has derivative 0 at almost every point of [0,1]
even though its strictly increasing.
I leave this for the readers (translation into English: I don't know the proof).
However, I emailed the author who emailed me the following:

There are proofs in the book Probability and Measure by Patrick
Billingsley. In the third edition, it's Example 31.1 on page 407.  The fact
that F is continuous and strictly increasing on [0, 1] is fairly easy to
see, based on the definition of the underlying random variable.  The fact
that F has derivative 0 is not as easy to see intuitively--the proof is
more of a hard analysis type proof.

The paper assumes that money is continuous and out lives are indefinitely long.
Ekhad, Georgiadis, Zeilberger have written a paper
How to Gamble if you're in a Hurry
that looks at these problems from (to quote their abstract) a purely discrete, finistic, and computational viewpoint.

Six Questions about unnatrual and natural mathematical objects

Today (Monday) I pose some questions. In my next post (Tuesday) I will post the answers
that I know (some I do not). Some questions are a matter of opinion
in terms of what you consider natural.

1. Is there a subset of [0,1] that is uncountable and has measure 0?
2. Is there such a set that is natural?
3. Is there a function that is continuous everywhere and differential nowhere?
4. Is there such a function that is natural?
5. Is there a function that has derivative 0 at almost every points of [0,1] even though it is strictly increasing?
6. Is there a natural such function?

I request that all comments be NON-anonymous.  (I'll tell you why when I post the answers I know on Tuesday.)

The Combinatorics of Batman

(I wrote this post about a year ago but waited until the new Batman
movie came out to post it. I haven't seen the movie yet so
there may more possibilities to add to this.)

There have been many versions of the BATMAN story:
comic books (and within that there are several versions),
many movies, and a TV series.
This may lead to a COMBINATORICS question you can ask your class.

So how many ways can the BATMAN story go?
This is NOT A QUIZ- all of the answers are correct
for some version of BATMAN.

1) As a child Bruce Wayne saw his parents gunned down.  What were they doing before this happened?

 a) Watching the movie Zorro.
 b) Watching the movie The Lone Ranger.
 c) )Watching an Opera.

2) Who shot Bruce Wayne's parents?

 a) Joe Chill- a low level mugger.
 b) Joe Chill- hired by the mob since Thomas Wayne (Bruce Wayne's father) had once foiled a crime. The orders were to leave the boy alive so it would look like a low level mugging.
 c) The gangster who would later become the Joker.

3) Who was the Joker before he became the Joker?

 a) A completely innocent chemist-turned-comedian.  He was a good man but a bad comedian. He was just going to do one theft to make ends meet. Things went wrong and he fell into a batch of chemicals and became The Joker.  He is now a bad man but a good comedian.
 b) A gangster who was sleeping with his bosses girlfriend.  The boss arranged for him to be killed ,but nstead the gangster falls into a batch of chemicals and becomes The Joker.
 c) Hey, its just makeup. But he has scars which may have come from his father, himself, or who knows?
 d) There are surely other versions I do not know.  One could probably write a bad PhD on this topic.

NOTE: I don't think the Jokers name is known in any of the versions.
(Contrast: The Riddler's name is Edward Nigma.)

4) Where is the Joker now?

 a) In Arkam Asylum.
 b) Dead.
 c) Gee, he really seemed to die but we just know he'll turn up again.

5) Who is Two-face?

 a) Harvey Dent, the DA, who was a good man. During a court trial a criminal throws  acid on his face. Now half of his face is scared. This drove him insane and he is now a criminal.
 b) Harvey Dent, the DA, who was a good man. Dent and his girlfriend Rachel Dawes are kidnapped.Batman and Commissioner Gordan save him but (1) Rachel dies, and (2) Dent has his face half disfigured.This drives him mad.
 c) There are about 5 other people who took on this role. One of them was named Harvey Kent.   No relation to Clark Kent

6) Who else lives in Wayne Manor?

 a) Robin, Alfred the Butler, and Aunt Hariet.
 b) Robin and Alfred the Butler.
 c) Just Alfred the Butler.

7) How well do Batman and Superman get along?

 a) Superman is never mentioned.
 b) They get along.
 c) They don't get along.
 d) They REALLY don't get along!


This leads to a combinatorics question and a Batman question.
COMBINATORICS: Assuming that all of these options are independent, how many versions of the
Batman Legend could there be? This should be easy.
BATMAN: Of all of these, how many have actually been realized?
This might take a Batman scholar to figure out.
And I haven't even talked about Robin (nor will I).

There are also variants of the COMBINATORICS question if you disallow certain
combinations. For example, If Aunt Hariet exists then Superman does not.

I'm sure there are more options I don't know about.
If you know any, comment!

CCC12- post 4 of 4- Misc Info.

CCC 12 post 4 of 4.
The business meeting and other observations.

1. Programming committee info:
   
   1. There were 119 submissions of which 18 were junk (more on that later). This is pretty large- Paris 2009 had 113 submissions. The junk papers were not so much papers that claim they proved P=NP or P\ne NP; they were papers where it is hard to know what they are claiming. (Hmmm- there are valid papers that, after you go through all the definitions, its not clear what they are claiming.)
      
   2. 34 papers accepted. Second highest to Paris having 37. (In both Paris and this year there was no Rump Session- that could be why, no time for one.)
      
   3. Andrew Drucker won Best Student Paper award for Limitations of Lower-Bound Methods for the
      wire complexity of Boolean Operators.
      
   4. See Prog Comm Chair Slides for more information.
      
2. There were roughly 60 people at the conference. Here is a list of all attendance figures up through 2008 (if you know of the attendance in the later years let me know and I will add them).
   
3. Steering committee:
   
   1. Johan Hastad and Manindra Agrawal have been on the committee but their term has expired so they are now off of it.
      
   2. The steering committee put Madhu Sudan on.
      
   3. An election by people at the meeting put Venkat Guruswami on.
      
   4. Peter Bro Miltersen is stepping down as chair (his term expired) and Dieter is the new chair. Peter will stay on one more year (I think).
      
4. Future Conferences:
   
   1. 2013: the conference will be in Palo alto, ca, co-located with STOC June 1-4 STOC, June 4-7 CCC. I WILL BE THERE!
      
   2. 2014: the conference will be in Vancouver. Local arrangements chair Valentine Kabanets. There were no competing bids (are there ever?) I WILL BE THERE!
      
   3. 2015: Depends on if there is an FCRC and if we join it. In any case I WILL BE THERE! The Steering committee will decide these things later.
      
5. This year there were electronic proceedings (I think for the second time.) That's good, and I'm glad we don't have paper, but I would prefer if the proceedings were available on a public website before the conference (SODA has done that) or at least after (if it IS available and I missed that- leave an intelligent comment about it). On the other hand this might not matter much since most of the papers are available on line anyway.
   
6. My posts on the content of the conference didn't get many comments, nor did I think they would. I hope they were useful to you. Forcing myself to do it was very useful to me, and for that I thank you, the readers. (For abstracts of ALL of the papers without my opinions, see here and press on abstracts (not on the left column).
   
7. On my Honeymoon in 1991 I went on a cruise and we were cut off from ALL news. When we got back the first thing I heard was The crisis is over, the tanks are leaving Moscow. This was somewhat alarming. They were referring to the 1991 Soviet Coup d'etat attempt. By contrast, in 2012 in Portugal, I heard about the Supreme Court Decision on Health Care within an hour of when it happened. I missed the earlier incorrect accounts. Is it a good or bad that its harder to get away from news coverage? Lance posted on a related topic a while back
   
8. I was gone for a total of 20 days and did not check email once. (i had a vacation problem on.) I came home to 474 emails of which 20 needed to be responded to. None of them were crucial.
   

CCC 2012- Post 3 of probably 4

Post 3 of n on CCC 2012. I still don't know what n is.
I summarize the third and fourth day of the conference.
(The fourth day was only a half-day).

Thursday June 27 Morning Session:

1. Matrix Lie Algebra Isomorphism by Grochow. This paper was called (and the link above still uses the old name) Lie Algebra conjugacy. Some Isom problems for Lie Algebras are equivalent to Graph Isomorphism. In general Harder Math does not mean Harder Computationally.
   
2. On Sunflowers and Matrix Multiplication by Alon, Shpilka, Umans. Erdos-Rado made a conjectures about sunflowers. Coppersmith and Winograd made a conjecture in combinatorics which would, if true, yield a better Matrix Mult Alg. This paper shows (roughly) that if the ER-conj is true then the CW-conj is false. Neither conj sounds that intuitive to me so I don't know what to make of this.
   
3. Algebras of minimal multiplicative complexity by Blaser and Chokaev. I couldn't find a link- if you know one email it to me.
   
4. Invited Talk Prospects for Geometric Complexity Theory by Peter Burgisser. So what are the prospects? Mixed. I was happy to hear that there are people working on this, but the talk was not that optimistic.
   

Thursday June 27 Afternoon Session:

1. A Strong Direct Product Theorem for Quantum Query Complexity by Lee and Roland. Direct Product Conjectures say (roughly) that if a problem takes T blahs to do then doing k of them given to you all at once takes kT blahs to do. There are many of these depending on your interest. This paper shows shows something stronger: If you want to computer just the XOR of the k instances it will take roughly kT quantum queries. (That is not quite right- there are a lot of details I left out.)
   
2. A Strong Parallel Repetition Theorem for Projection Games on Expanders by Raz and Rosen. A parallel repetition theorem usually says that if the prob of (say) winning one game is p, then the prob of winning n games is pⁿ (That can't be quite right but that's the idea). The real question is how fast does the prob go down. This paper adds to our knowledge on this.
   
3. Share Conversion and Private Information Retrieval by Beimel, Ishai, Kushilevitz. I couldn't find an online version. If you know of one email the link please. The paper claims to unify and simplify PIR protocols!
   
4. Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Game by Aydinlioglu and van Melkebeek. There have been theorems along the lines of Lower bounds imply Derand. There have also been some (and this is one of them) along the lines of Derand implies Lower Bounds. As the author points out, when you first hear the result you may think one of two things: (1) GOOD NEWS- to get lower bounds, all I have to do is Derandomize! (2) BAD NEWS- to derandomize I HAVE to prove lower bounds, which are hard to prove. He claims a third interpretation of his paper- if you can derandomize then you can do so in a nice way
   
5. Hitting Set Generators for Sparse Polynomials over any Finite Fields by Lu. I could not find a link- if you know one email it to me.
   
6. Pseudorandom Generators for Read-Once ACC0 by Gavinsky, Lovett, and Srinivasan. Or see the talk on video from IAS.
   

Friday June 28 Morning Session

1. Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification by Cohen, Raz, and Segev. An extractor (informally) takes two strings and outputs a string that looks random. Strong Extractors and non-malleable extractors are stronger notions. Non-malleable extractors produce strings that look random, even to an adversary who is trying to make trouble. Hence they are good for Privacy Amplification. This paper has unconditional constructions of them!
   
2. Better Condensers and new extractors from Paravaresh-Vardy Codes by Ta-Shma and Umans I lose track of condensers vs extractors vs expanders vs dispersers.
   
3. List Decoding Barnes-Wall Lattices by Grigorescu and Peikert List decoding is when, instead of finding what a string decodes to, you find a small set of candidates, one of which is correct. What is a Barnes-Wall lattice? The paper does a good job on this. I wonder if the original paper by Barnes and Wall does as good a job?
   
4. Space-efficient algorithms for reachability in surface-embedded graph by Stolee and Vinodchandran. One of the consequences of there results is log-space algorithms for some graph-reachability problems. Maybe L=NL!
   
5. Space Complexity in Polynomial Calculus by Filmus, Lauria, Nordstrom , Thapen, Zewi. Proof complexity. While lower bounds on Resolution are well understood, what about more powerful proof systems? This paper is a good start on that.
   
6. Combinatorial PCPs with Short Proofs by Or Meir.
   I wish the PCP theorem itself had a short proof. Perhaps you can prove that it does.
   

CCC 2012: Post 2 of n

CC 2012. I still don't know what n is.
I summarize the second day of the conference.

Wednesday June 27 Morning Session:

1. A Satisfiable Algorithm and Average Case Hardness for Formulas over Full binary Basis
   by Seto and Tamaki.
   
2. Approximating AC
   by Beame, Impagliazzo, Srinivasan.
   
3. DNF Sparsification and Faster Deterministic Counting by Goplan, Meka, Reingold.
   

All three of the above papers solve a hard problem in slightly-better-than the usual worst case. All three of them (I think) want to use this to obtain lower bounds. (Recall that this is ultimately how Ryan got his lower bound- via an algorithm. I want to see a SODA paper that gets an algorithm via a lower bound.) Something bothers me about this. If we are getting algorithms that beat (albeit, just barely) brute force search, perhaps we should be yelling MAYBE P = NP instead of LETS USE THIS TO SHOW THAT P ≠ NP. Just a thought.

1. Invited talk Communication Complexity and Information Cost: Foundation and New Directions by Toniann Pitassi.
   This was an excellent talk. I didn't realize it was an hour long invited survey talk instead of a 20 minute long normal talk.
   I kept waiting for
   (a) her results, and (b) the talk to end, even though I was enjoying it.
   ADDED LATER: Toni emailed me her slides.
   They are
   here
   

Wednesday June 27 Afternoon Session:

1. Gaussian Noise Sensitivity and Fourier Tails by Kindler and O'Donnel. They first define a new kind of sensitivity Rotation Sensitivity They then show that this type of sensitivity is subadditive. This is used to obtain simple (or at least simpler) proofs of the the Gaussian Isoperimetric inequality in certain cases and a lower bound on approx max-cut of .8787 (not the best known, but very close and a simpler proof).
   
2. Junto-Symmetric Functions, Hypergraph Isomorphism, and Crunching by Fischer, Garcia-Soriano, Matsliah. Two Boolean functions are Isomorphic if they are the same up to a relabelling of the variables. Given two Boolean functions, can we tell if they are isomorphic? One way is to obtain the truth table for both of them and then see if some permutation of the variables makes them the same. Even if all we care about is queries, this seems like a lot. Can we do this in less queries? That is, we are asking Property Testing questions. What if we restrict them. Then what? Read the paper to find out!
   
3. Complexity lower bounds through Balanced Graph Properties by Moshkovitz.
   This looks hard! They mention Tensors!
   
4. Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators by Andrew Drucker. First there were pathetic lower bounds on wire complexity. Then after what seemed like half a century, there were (just recently) some slightly less pathetic lower bounds. Even so, that was promising. This paper shows NO, don't get too excited. The new technique will not get better results. Gee Andy Drucker, couldn't you have let us dream just a bit longer. The most depressing talk I have every seen. (It was a GREAT talk and a GREAT result, but still depressing.)
   
5. Limits on Alternation-Trading Proofs for Time-Space Lower Bounds Fortnow, Lipton, van Melkebeek, Viglas showed that any algorithm for SAT that uses log space must take at least time n^1.61 (the golden ratio). Since the golden ratio is a natural number (not literally) it was plausible that current techniques could not improve that. But Ryan Williams got n^c where c is 2cos(π/7) which is roughly 1.801. This can't possible be the best we can do since its just such a funny looking number. Ryan Williams wrote a program to try to fine tune the constants and do better but he couldn't do better. So he said NOBODY can do better!!!!. His advisor Manuel Blum believed him, but nobody else did. NOW he has shown, with help from Sam Buss, that NO, nobody can do better. I am impressed that he and Sam Buss were able to formalize what the technique was in a way that really does pin down ALL prior proofs. Had this paper been written first, there would only be one paper. This talk was NOT depressing since, being a new problem, I can believe that Ryan or Sam or someone can look at what the old techniques were and come up with some new ones and break the (I can't believe I am writing this) 2cos(π/7) barrier! And then what? A paper showing that that bound can't be improved, and then improve it. How far can this go? I've heard that really, really, we won't be able to show quadratic lower bounds. We'll see.
   
6. The Hardness of Being Private Common problem in crypto: Alice has x, Bob has y, they want to computer f(x,y) but they can't know anything about the other ones input accept what they can learn from their input and f(x,y). Are there any functions that people really want to compute like this? YES- the functions involved in a Vickrey Auction. In a Vickrey auction Bob and Alice bid x and y privately. The winner pays the LOSING bid. So if Alice bids 1000 and Bob bids 100, Alice gets to buy it for 100. Formally f(x,y) contains both WHO won and what they paid. The winner does know what the loser bid. But the loser should not know what the winner bid. This paper is about computing this function approximately-private in both the worst case and the average case. The most practical paper at the conference which isn't saying much. (Can the winner use Quantum Money?)
   

CCC12: Post 1 of n

(Post 1 of n on CCC 2012. I don't know how large n is yet.)

I will discuss the papers in the order they were presented.

June 26, 2012. Morning

1. Amplifying Circuit Lower Bounds Against Polynomial Time with Applications by Richard Lipton and Ryan Williams. Of course, what we mean by Applications may differ from what other people call applications. Here is one of the two main results:
   
   

   Let c,d ≥ 1 and e < 1 such that c < (1-e+d)/d. Either QBF is not solvable in time n^c or the Circuit Eval problem cannot be solved with circuits of size n^d and depth n^c.
   

   
   This is one of those odd results where its and OR of two things that we think are both true. But there are two unconditional lower bounds that can be derived from it:
   
   
   1. QBF does not have O(n^1.618)-time uniform circuits of depth n^o(1).
      
   2. For all ε > 0, QBF does not have O(n^{2- ε})-time uniform circuits of depth n^o(1).
      
   In his talk Ryan said that he needed the kind of complexity that only people like Dick Lipton still remember. (ADDED LATER: This is a misquote, see Ryan Williams comment below.)
2. Is the Valiant-Vazirani Isolation Lemma Improvable? By Holger Dell, Valentine Kabanets, Dieter van Melkebeek. Probably not. Oh well.
   
   
3. Parallel Approximation of min-max problems with application to classical and quantum zero-sum games by Gus Gutoski and Xiado Wu. In this paper they developed a better solution to a classical problem and then applied it to a quantum problem. I don't think this is common-- do you know of any other examples?
   
   
4. On the complexity of the Separable Hamiltonian Problem by Andre Chailoux and Or Sattah. (The first name is Or.). This paper looks hard!
   
   
5. Quantum Money with Classical Verification by Dimitry Gavinsky. Quantum Money is a funny topic in that it may be feasible in 100 years, but by then we will all have e-money.
   
   

Afternoon:

1. The Usefulness of Predicates by Per Austrin and Johan Hastad. There is an hour-long version of the talk done on a blackboard here.
   
   li> Reductions between Expansion Problems by Prasad Raghavendra, David Steurer, and Madhur Tulsiani. The authors claim that the Small Set Expansion Hypothesis (SSEH) is a natural hypothesis. (It has been discussed in earlier papers.) This paper shows that SSEH is equivalent to a subcase of UGC. The authors claim that SSEH is is the combinatorial heart of the UGC. WOW!
   
   
2. On Problems as Hard as CNFSAT by Marek Cygan, Holger Dell, Daniel Lokshantov, Daniel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabi, Magnus Wahlstrom, The Strong Exponential Time Hypothesis (SETH) states that for every ε > 0 there exists k such that k-SAT cannot be solved in time 2 ^{ε n} This paper assumes SETH and proves from it lower bounds on HITTING SET, SET SPLITTING, and NAE-SAT.
   
   
   
3. Testing List H-Homomorphisms A List H-Homomorphism is (informally) a homomorphism that satisfies given constraints. Given the constraints and given oracle access to an alleged hist H-Homomorphism, we want to determine if it IS one or is FAR FROM being one (if its not one but close we don't care.) As usual in property testing we are concerned with O(1) queries and sublinear queries. Both are characterized.
   
   
4. A Dichotomy for Real Weighted Holant Problems. by Sangxia Huang and Pinyan Lu. Recall that in Valiant's paper Accidental Algorithms he showed that for monotone planer 3-CNF formulas where each var appears twice (1) finding the number of solutions mod 2 is parity-P complete, but (2) finding the number of solutions mod 7 is in P. Since then there has been a wave of research trying to classify which counting problems are hard (likely complete somewhere) and which are on P. The paper by Huang and Lu is a big jump in this field.
   

North Carolina tries to legislate science

(I will post on CCC 2012 next week. I am still recovering from Jet Lag and going
through 472 emails that piled up on 2.5 weeks, of which 22 were relevent.)


You may have heard the story about the state of Indiana Pi bill:
In 1897 the state of Indiana wanted to legislate a value of pi.  Before reading the true story
I had heard the following:

1. They wanted to legislate pi=3 since the bible says that pi=3.  (The Bible does have a passage that seems to say pi=3, though that may not be the right interpretation.
   See here.)This version of the story puts them in a bad light.
2. They wanted to legislate pi=3 since this makes calculations easier.  They didn't really say pi=3, just that when measuring wheat in silos (or some such) everyone uses pi=3 to make everyones calcuations uniform and easy. (This was in the 1880's- they didn't have Wolframs Alpha).  This version of the story puts them in a good light.

Neither version is true. Look up the link to see what really happened.  Could this happen in America today?
On two issues it certainly could: Evolution and on Climate Change.

The North Carolina House has passed a law saying HOW to predict sea level rise rates.
The method they require predict less sea level rise then... anyone else. And only the
Division of Coastal management is allowed to put out such numbers.  So Independent scientists are not allowed to use... the scientific method.  (Not sure how they will enforce that.) See here for details.

Who wins, who loses?

1. Colbert gets a nice bit about it (which is how I learned about it): here
2. I get a blog out of it.
3. Scientists have to publish less, thus less trees get cut down, so the environment wins.
4. North Carolina looks more ridiculous than Indiana did back in 1897. But there are two differences-
   (1) North Carolina understood what the bill was saying and still passed it, Indiana did not.
   (2) North Carolina's bill has actual policy consequences, Indiana's pi-bill wouldn't have.
   

Fortunately the North Carolina Senate did not pass the bill so its not law. Yet.

Why is it called the Turing Award?

The ACM Turing Award represents the highest honor in the computing research community, the closest we have to a Nobel prize in computer science. In this centenary celebration of Alan Turing, it seems obvious that the award should be named after him.

But back in 1966 when Alan Perlis won the first Turing award, Turing's influence on the field was far less obvious. Turing's model had only a few years earlier found its way into computer science literature, still dominated by automata, parsing and circuits. In 1966, what is now the Foundations of Computer Science conference was just renamed Switching and Automata Theory from Switching Circuit Theory and Logical Design.

So why name the award after Turing back then? This question came up during one of the panel sessions at the ACM Turing Celebration where there were some vague guesses. I asked around during the breaks and nobody seemed to know. I even put the question to Turing biographer Andrew Hodges in Cambridge and he similarly didn't know.

The Knuth prize aside, most awards are named after people who have passed away. Back in 1966 there weren't very many dead computer scientists. Even among Turing's generation, Church, Post, Kleene, even Gödel were alive and kicking. Turing would have only been 54 had circumstances been different. John von Neumann died young from cancer in 1957 but wasn't thought of primarily as a computer scientist. There were also Charles Babbage and Ada Lovelace but I'm not sure they were in people's minds back then.

I'm guessing that Turing was just the default choice for the name of the award and the ACM just got extraordinarily lucky for picking the right person in spite of themselves.

Instance Compression

Some announcements: FOCS Accepts, ITCS Call and ToC Special Issue for Rajeev Motwani

I'd like to highlight one of the new FOCS papers "New Limits to Classical and Quantum Instance Compression" by MIT student Andrew Drucker which solves a problem that has dogged me for a few years. Ignore the "Quantum" in the title, that's not the interesting part.

Consider the OR-SAT problem, given m formulas each of size n, is at least one of them satisfiable. In STOC 2008, Rahul Santhanam and I showed that if there is a reduction from OR-SAT to any language L with the property that the reduction reduces to instances of size polynomial in n (independent of m) then the polynomial-time hierarchy collapses. The question arose from parameterized complexity though it also has some applications to cryptography and PCPs.

Our techniques failed to get a similar result for AND-SAT, where we want to know if all of the formulas are satisfiable. Drucker settled the question, showing that a compression of AND-SAT (reducing to instances of size polynomial in n) also gives a similar collapse of the hierarchy. What impressed me the most was the ingenuity Drucker uses in his proof.

Drucker derives the following lemma about probability distributions based on a strong version of Fano's inequality. Let A be a set of strings, D a distribution over A and f any function that maps A^m to {0,1}^m-2. If you pick a y from D, with high probability there is an index i, such that the distributions f(D^m) and f(D^m) with the ith location replaced by y are statistically close.

Drucker combines this lemma with a minimax argument and a result of Sahai and Vadhan that characterizes Statistical Zero-Knowledge as determining whether two distributions are different from the circuits that generate them.

Sometimes people solve your open questions with a simple argument that makes you hit your head for not thinking of it yourself. Other times you just sit back amazed at the solution knowing there was no hope for you to find it. Drucker's paper definitely falls in that second category.

Transitions

On July 1 I officially move jobs from Northwestern to Georgia Tech, a change not just in location but in role as I become a department chair.

I'm proud by what we put together in my 4 1/2 years at Northwestern, a strong group at the intersection of CS and Economic theory with Jason Hartline, Nicole Immorlica and great connections with the economists at Kellogg, the Northwestern business school.


So why leave? I've been thinking about taking on a more leadership role at this point in my academic career and when Georgia Tech came calling it was impossible to turn it down. But all moves are bittersweet and I'll truly miss the atmosphere we put together at Northwestern.


Also in the CS community, on July 1 I pass the mantle of SIGACT chair to Paul Beame. In exchange I'm joining the CRA board on that date.

This is a week of many conferences, ICML in Edinburgh, LICS in Croatia, Women in Theory in Princeton and the blog's namesake Computational Complexity in Porto. Having attended the first 26 meetings of the Complexity conference I miss it for the first time. Bill is there and hopefully he'll come back with a full report.

Eric Allender remains the only person to have attended every Complexity conference. "I'll continue to go as long as they are fun", he remarked last week. May he have reason to go for many more years.

Which brings me to the saddest transition of them all. Manfred Kudlek, retired professor at Hamburg, passed away on the bus for the excursion to Betchley Park last Monday during the Computability in Europe conference. Manfred is well known as the only person to have attended all 38 ICALP conferences, the Warwick meeting next month will seem empty without him.

Alan Turing (1912-1954)

Today we celebrate the 100th anniversary of the birth of Alan Turing, remembering his incredible life and mourning his tragic death. Alan Turing simply asked how does a mathematician solve problems. He developed such a simple model, now called the Turing machine, that so perfectly captures computation and years later would be the right model to capture computational complexity.

Alan Turing did so much more, codebreaker, computer builder and developer of his test of intelligence, that he so richly deserves the title "father of computer science". But it is the Turing machine that gives us the right notion of computation, both formal and intuitive and the foundation for a whole new research field.

A week ago ACM honored Turing by bringing together 32 recipients of the Turing Award, the highest honor in computer science. An incredible retrospective on Turing's influence on computer science from those who best followed in Turing's footsteps. You can celebrate the day by watching the webcast. I recommend the panel sessions on the Turing Computation Model and the Algorithmic View of the Universe. Just seeing these great theorists on stage together is a treat.

Today I have to privilege to celebrate Turing's legacy in Cambridge, England, where the Computability in Europe conference ends its meeting at King's College of Cambridge University. Turing was an undergraduate at King's College when he developed the computational model and wrote his truly classic paper. Everyone should read Chapter 9 where Turing gives an amazing argument why his model captures computation.

Thank you Alan. The world computes because of you.

The Ketchup Problem

MIT scientists are working on a bottle of ketchup where you CAN get out every last drop.  See here for details and some nice videos of the new bottle in action. This will be used on other products (like Mayonnaise) and will save much thrown away food every year! However, IF this had been around 45 years ago, then I might never have gone into Math!!! Why is that?

When I was 8 years old I had the following thought:

When ketchup is at the end of the bottle it drips very slowly.  It never stops dripping hence the number of drops is infinite.  Could I put an empty bottle of ketchup below it and catch all of those drops and hence never run out of ketchup?

When I was in college I came up with the following explanations:

1. NO: By the same reasoning there will never be an empty bottle of ketchup!
2. NO: Each drop is half the size of the previous one so even though this is an infinite series it converges.
3. NO: The time between drops doubles so it would take infinite time to fill up another bottle.

To this day I will NOT give up my conviction that the number of drops is infinite.  This ketchup problem may be the first time I saw a real world phenomena and made a math problem out of it. I blogged about other such problems here and here.
The ketchup problem so intrigued me that I became a math major. OR the fact that I thought of this problem indicates that I liked math and hence went into it. I would say its a chicken-and-egg thing but we need a new metaphor since
the chicken came first.

Other questions I thought of as a kid:

1. Why do people smoke tobacco if its so well known that its bad for them?  This one still puzzles me.
2. If, as the TV ads indicate, people want Margarine that tastes JUST LIKE BUTTER then why not just get butter? I NOW know that Margarine was cheaper back then (still is).
3. If, as the TV ads indicate, people want instant coffee that tastes JUST LIKE GROUND ROAST, why not just get ground roast? I had no idea what any of those terms meant as a kid. Why I cared is a mystery since I didn't drink coffee as an 8 year old (and I still don't).  I now deal with math terms i don't understand. Why I care is a mystery.
4. How is eating everything on my plate going to help the kids that are starving in Africa? Mom never quite answered that one.
5. How come whenever I see six kids playing together there are always either three that get along or three that don't get along?

Had I pursued the first three questions I would either be in sociology or advertising. Had I pursued the fourth question I might be in economics or politics. I have no idea what pursuing the fifth question would have lead to. Child Psychology? Party planning?

READERS- do you recall a math problem that you cared about as a kid that likely either inspired you to do math or indicated that you were interested in math? Note that you don't need to have SOLVED the problem as a kid- I am interested in your interests,
not your ability (note that I didn't any of my problem as a kid).

Name My Book

As many of you know I have been working on a non-technical popular science book on the P versus NP for a general audience. The book is mostly finished but the biggest challenge is finding a good title.

The current working title is

The Golden Ticket: P, NP and the Search for the Impossible

The “Golden Ticket” refers to beginning of the Roald Dahl book Charlie and the Chocolate Factory (and the two movies based on the book) where everyone is searching for a golden ticket to get a factory tour. But the publisher is worried that people will not understand the reference until they read the book.

Here are other possible titles some from me and many from the publisher.

• P vs NP: The Search for the Impossible
• Finding the Needle: P, NP and the Search for the Impossible
• The Road to Nerdvana: P, NP and the Search for the Impossible
• The Second Most Famous Equation: P=NP and the Search for the Impossible (the first being E = mc²)
• Can We Solve It? : P, NP and the Search for the Impossible
• The Ultimate Math Problem: P, NP and the Search for the Impossible
• How to Solve Everything and Why It's a Bad Idea: P, NP and the Search for the Impossible
• The Most Important Equation You Never Heard Of: P=NP and the Search for the Impossible
• The Answer to Everything
• Impossible Math: The search for the solution of P, NP
• One equation to rule them all: P, NP and the Search for the Impossible 
• One Way Math: P, NP, and the Search for the Impossible
• The Ultimate Puzzle: P,NP and the Search for the Answer to Everything
• The Golden Ticket: The Impossible Equation that Could Solve All Problems
• The Answer to Everything: The Ultimate Unsolvable Equation
• The Golden Ticket: The Ultimate Unsolvable Equation that Could Be The Answer to Everything 

Honestly I'm not loving (or hating) most of them. We decided to ask my readers, many of you are in the target audience for the book. Any of the titles above that you truly love (or hate)? Or do you have another suggestion? If we use your title, a free signed copy of the book will be yours.

Do 50-1 longshots in the Kentucky Derby ever come in?

(I delayed posting this until after The Belmont Stakes since I wanted to see if there would be a Triple Crown winner.
Alas, I'll have another was scratched. From what I've heard it was the right decision.)

Watching the Kentucky Derby my wife asked Do  50-1 shots every win? Since the Derby has been run 138 times it is likely that a 50-1 shot came in at least once.  That is, of course, if the odds were correctly figured.  Were they?

Essentially yes.  For the  ten longest longshots to win the derby I call a horse UNDERVALUED if they showed (came in 1st or 2nd or 3rd) in at least one of the other legs of the Triple Crown, and FLUKE if not. If there are other reason to say FLUKE I do so. Sometimes I say DON"T KNOW.

1. Donerail won in 1913 and was 91-1. (The longest long shot to win.) The prob that a 91-1 shot would NEVER come in after 138 races is (1 - 1/91)¹³⁸ which is roughly 0.217647740202952.  So while this is possible, it's more likely that such a long shot would come in. I could not find information on if Donerail ran in the Preakness or the Belmont Stakes.  Even though I don't know I'll say FLUKE with odds that long.
2. Mine that Bird won in 2009 and was 50.6-1 The prob that a 50.6-1 shot would NEVER come in after 138 races is (1 - 1/50.6)¹³⁸ which is roughly .0636355836570341.  Extremely unlikely, hence not at all surprising that such a horse won at some point, though surprising when it happens.  He finished second in the Preakness and third in the Belmont Stakes. UNDERVALUED!
3. Giacomo won in 2005 and was 50.3-1. Two horses that were roughly 50-1 have won the Derby.  I leave it to the reader to calculate the prob that only one 50-1 horse wins. I suspect that it is quite low, so having two of them win is reasonable.  He finished third in the Preakness and seventh in the Belmont Stakes. UNDERVALUED. I recall at the time thinking that betting he would show in the Belmont Stakes would be a sure thing. Alas, there is no such thing as a sure thing.
4. Gallahadion won in 1940 and was 35.2-1 (The website mislabels the picture as being from 2005 and misspelled the horses name by leaving out the a after the ll. What are the odds of that?) He finished third in the Preakness and did not show in the Belmont Stakes.  UNDERVALUED.
5. Charismatic won in 1999 and was 31.3-1.  He won the Preakness and came in third in the Belmont Stakes. UNDERVALUED!
6. Proud Clarion won in 1967 and was 30-1.  He finished third in the Preakness and Fourth in the Belmont Stakes. UNDERVALUED.
7. Exterminator won in 1918 and was 29.6-1.  Wikipedia has nothing on the Preakness or Belmont Stakes, so I assume he didn't run them. DON"T KNOW
8. Dark Star won in 1953 and was 24.9-1. A better name would have been Dark Horse. Was fifth in the Preakness possibly because he got injured running it, and that injury ended his career. DON"T KNOW.
9. Thunder Gulch won in 1995 and was 24.5-1. He came in third in the Preakness and won the Belmont Stakes. UNDERVALUED!
10. Stone Street won in 1908 and was 23.7-1.  Wikipedia does not have anything about his performance in the Preakness or the Belmont Stakes so I assume he didn't run in them. Wikipedia DOES report that his time, 2:15 1/5 is the slowest winner ever of the Derby. Based just on this I say FLUKE.
11. Animal Kingdom won in 2011 and was 20-1. He finished second in the Preakness and didn't show  in the Belmont Stakes (I could not find how well he did).  UNDERVALUED

Some comments:

1. To answer my wife's question- in 138 Derbies a 50-1 or better shot came in 3 times, which I think is about right, or at least not surprising. So they DO win.  Sometimes.
2. I was surprised that 5 of the 10 longest longshots were since 1999.  I would think people know more about racing now and so a real long shot is less likely. That may be the wrong way to think about it.
3. Should you bet on longshots? If you always bet x on the longest longshots in the Kentucky Derby, and (I have not checked this) The first, second, and third on the list above were the longest longshots when they ran, you would have roughly 190x - 135x = 55x dollars.
4. How do you tell if a long shots is undervalued (the odds should have been better) or a fluke (the odds were correct but something weird happened)? Here are three ways: (1) See how they did in the other two legs of the Triple Crown, (2) See their runtime in the Derby, or (3) for each race see if there were odd odd circumstances. For example, sometimes, it all depends if it rained last night.
5. By my measure there were six undervalued, two flukes, and two don't knows. I don't know if this means my measure is wrong.
6. Actually I'm GLAD that long shots sometimes come in. If not then they are being overvalued.  This is similar to why David Pennock wrote Why we're happy we got one prediction wrong on Super Tuesday. I saw his talk the same week as the Derby, and both jointly inspired this post. What are the odds of that?
7. I asked Dave Pennock about these issues and got two interesting thoughts from him:
   
   
   
   1. There is evidence racetrack odds are just about right (efficient) except with a slight "favorite-longshot bias" where favorites win a little too often and longshots not quite enough (people bet a little more than they should on longshots).
   2. It is an interesting hypothesis that odds should be less long with more information. I'm not sure that's true. With more information, the entropy of the distribution should go down, which intuitively might lead to longer long shots (and surer sure things)?
8. Dave also told me that there has been A LOT of work on this.  Here are some references:
   
   
   
   1. There is a whole edited volume on the subject: Efficiency of Racetrack Betting Markets
   2. Horse racing Testing the efficient markets model by Wayne W. Snyder.  J. of Finance, V. 33, No. 4, 1978.  pp. 1109--1118.
   3. Probability and utility estimates for racetrack bettors by Mukhtar M. Ali. J. of Political Economy, V. 85, No. 4, 1977, pp. 803--816.
   4. Utility analysis and group behavior: An empirical study by Martin Weitzman.  J. of Political Economy, V. 73, No. 1, 1865, pp. 18--26.
   5. Anomalies: Parimutuel betting markets: Racetracks and lotteries by Richard H. Thaler and William T. Ziemba.  J. of Economic Perspectives, V. 2, No 2, 1988, pp. 161--174.
   6. Gambling and rationality by Richard N. Rosett.  J. of Political Economy, V. 73 No. 6 pp. 595-607, 1965.
   7. Informed traders and price variations in the betting market for professional basketball games by John M. Gandar, William H. Dare, Craig R. Brown, and Richard A. Zuber.
   8. Information incorporation in online in-game sports betting markets by Sandip Debnath, David M. Pennock, Steve Lawrence, Eric J. Glover, and Lee Giles.  Proceedings of the Fourth Annual ACM Conference on Electronic Commerce, pages 258-259, 2003.
   9. How accurate do markets predict the outcome of an event? the Euro 2000 soccer championships experiment by Carsten Schmidt and Axel Werwatz.  Technical Report 09-2002, Max Planck Institute for Research into Economic Systems, 2002.
   10. Here are some fun books on the subject: Sharp Sports Betting by Wong and Calculates Bets by Skiena. I reviewed Skiena's book in my SIGACT NEWS book review column here.
   
   

Fortnoy's Complaint

During my daughter's 8th grade graduation last week, the teacher reading the names said "Molly Fortnoy...I mean Fortnow". I felt for Molly. When my name was first mentioned in a conference talk back in 1986 the speaker also said "Fortnoy". For the record my name is pronounced as it is spelled, like "He's going to the fort now".

I've been called Fortnoy many times from people in my generation or older. I put the blame on Philip Roth's book Portnoy's Complaint.

My father's birth name was Paul Fortunow. The name has Russian roots, possibly connected to Fortunoff. The 'u' in Fortunow is silent. Go ahead and try and pronounce Fortunow. You forgot the "u" was silent. So a couple of years before I was born (and before Portnoy's Complaint) my father changed his last name to Fortnow.

Foreigners usually have no trouble pronouncing my name. But once when I was checking in at the Frankfurt airport, the agents said something like "Here are your tickets Mr. Fornow". I said "Thanks but that's Fortnow". She responded  "If it was pronounced Fortnow there would be a 'u' after the 't'". I should have asked her where she was from. 

A new bound on 3-hypergraph Ramsey Number! Why wasn't it discovered earlier?

When a new result is first discovered one question to ask is Why wasn't it discovered earlier? We look at a result in Ramsey Theory from 2010 and speculate as to why it was not discovered earlier.

Let R(k) be the least n such that no matter how you 2-color the edges of the complete 3-hypergraph on R(k) vertices there will be a homogenous set of size k (that is, a set H of size k such that all 3-sets from H are the same color). R(k) is known to exist by Ramsey's theorem.

1. Ramsey's original proof (in 1930) gave astronomical tower-like bounds on R(k).
   
2. Erdos-Rado (1954) showed that R(k) is bounded by 2^24k.
   
3. Conlon-Fox-Sudakov (2010) showed that R(k) is bounded by 2^22k. (They did a lot more in their paper- they looked at asymmetric 3-Hypergraph Ramsey Numbers and developed a new framework for them.) See Hypergraph Ramsey Numbers on that page.)
   

Why are these results important?

1. An improvement on the 3-hypergraph Ramsey numbers automatically gives an improvement in the a-hypergraph Ramsey numbers for any a ≥ 3.
   
2. There is an exponential gap between the upper and lower bounds of R(k) and all of the a-hypergraph Ramsey numbers. Hence any improvement may be a key to closing that gap.
   

I have (with Andy Parrish and Sandow Sanai) celebrated the result of CFS with a survey of bounds on the 3-hypergraph Ramsey Numbers here. Proofs and intuitions and historical context of the results enumerated above are in our survey. (If you read it and have corrections please email them to us- we plan to put it on arXiv next week.) The techniques in this paper did not depend on any mathematics unknown to Erdos or Rado (or others) in 1954. (This is in contrast to, say, Conlon's paper A New Upper Bound on Diagonal Ramsey Numbers which uses quasi random graphs- a technique and technology unknown in 1954.) So why didn't someone else prove the result earlier? Our speculations may apply to other results that are proven with techniques that were already known.

1. The CFS paper develops a framework for upper bounds on asymmetric 3-Hypergraph Ramsey numbers that involving a game (not a FUN game, but a game). This framework is used to prove many things. If all you want is the bound on R(k) then you don't need the framework and you get a proof that, IN HINDSIGHT, gives you the bound in a way that Erdos-Rado could have done. That's alot of HINDSIGHT. (Our Survey gives the stripped down proof of just that result, without their game framework.)
   
2. Not that many people worked on it. Hence that individual people didn't get it is not surprising. Perhaps Erdos-Rado was happy enough to get the bound from tower to merely 2^24k. More generally--- if an entire community is looking at a problem then the question Why wasn't it found earlier? may have a global answer. If its just a few people, it could just be local things like After working on this problem she switched to Computable Algebraic Topology.
   
3. CFS are very very clever. This is another HINDSIGHT argument- AFTER its done it looks easy.
   

Other reasons that might apply in other cases, though not to the case at hand:

1. Timing and Luck should not be underestimated. A paraphrase from The Honors Class: Hilbert's Problems and their Solvers, the chapter on Hilbert's 10th problem, page 112:
   

   All of these people, Robinson, Davis, Putnam, others had been reading Number Theory books full of obscure facts. Matiyasevich had just read the third edition of Nikolia Vorob'ev's ``popular book'' Fibonacci Numbers. In that book, published in 1969, there was a new result about the divisibility of Fibonacci numbers. Matiyasevich used it to prove If F(n)² divides F(m) then F(n)divides m. This allowed him to solve Hilbert's 10th problem (building on work of Davis-Putnam-Robinson). Robinson had read that book, but not the third edition!

   With the web is this more or less likely to happen? I ask nonrhetorically. (The spelling I give for Matiyasevich is the one given in the book. I have seen different spellings.)
   
2. Everyone thought the negation was true. This was one reason why NL=coNL was proven as late as it was.
   
3. The problem itself wasn't looked at earlier. Some of the Time-Space tradeoffs for SAT may be in this category.
   
4. A groupthink sets in and people are all thinking the same way. Laszlo Babai noted this concern in his 1990 article Email and the unexpected power of interaction where he writes:
   

   But will the diversity of thought that now exists be preserved in an era when intellectual fashions are dictated by the strongest? Shall we see more Levins and Razborovs come out of the Kolmogorov school, bringing in so prominently different, yet profoundly relevant ideas?

   He was referring to email, but the tendency of groupthink may be even more of a tendency with the web. (Levins and Razborovs, not Levin's and Razborov's, is how it appears in the original article.)
   

SO, READERS- your turn! Leave comments on results that, once proven, the question arose Why wasn't this proven earlier? and speculate as to why. You need not write a survey of the area.

Mihai Pătraşcu (1982-2012)

Update: Visit the Memorial Website

Mihai Pătraşcu passed away Tuesday after a bout with brain cancer. Even though he hadn't reached his 30th birthday, he had already produced a number of major achievements in the algorithmic community. The theoretical computer science community lost one of its brightest young stars.

During STOC, Yevgeniy Dodis arranged to have Mihai at the business meeting while we announced him as a co-winner of the EAPresburger award which Mihai will receive posthumously at ICALP next month. The standing ovation that followed made for the most emotional moment I have ever seen at an academic conference.

We asked Mohammad Taghi Hajiaghayi to write some personal thoughts on Mihai:

Last night I heard the very sad news that Mihai Pătraşcu has passed away at the age of 29. Though I knew about his cancer from 1.5 years ago and several steps that he took to fight the cancer still the news was quite shocking to me. Mihai's carreer was short but very productive with his lots of great papers in e.g., STOC, FOCS, and SODA.


Indeed Mihai is the second close friend of mine and a bright star researcher from my MIT times that I missed in the recent years (the first one was Misha Alekhnovich who died in 2006 in a white-water kayaking accident in Russia).


I became familiar with Mihai since 2002 when he joined MIT. He was interested in working on date structure with Erik Demaine who was my Ph.D. advisor as well. As a result, I got know him much better esp. since both of us had common experiences in IOI (International Olympiad in Informatics). One of Mihai's early ground-breaking papers is

Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu: Dynamic Optimality - Almost. FOCS 2004: 484-490

In this paper, an O(lg lg n)-competitive online binary search tree is given which improves upon the best previous competitive ratio of O(lg n). This was the first major progress on Sleator and Tarjans dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist. Indeed Mihai could formulate the O(1)-competitive conjecture as an approximation factor of some algorithm and we worked together for some time to prove the conjecture (that so far we could not:)). This was my first research experience with Mihai. Since then we always have talked about research (but we never had a joint paper).


In general Mihai and I were close friends and talked about all things. For example some times the people asked me about Mihai's personality especially because of some posts in his blog that were a bit controversial. I always told them Mihai is a very nice guy to work or chat with and those posts are indeed some concerns that everyone has in this mind, but Mihai is just brave enough to mention them loudly in his blog for the hope of some changes in the way that our community think (and anyone else including myself may agree or disagree with them).


After Mihai's graduation with Ph.D. from MIT which was only for 2 years (the same was true for Misha Alekhnovich), he applied for lots of places and got several very good offers. I was one of the people who encouraged him to join AT&T research labs, the place that I was there at that time. Finally Mihai decided to decline several faculty offers and join AT&T esp. to work with Mikkel Thorup (before joining AT&T he went as a Raviv Postdoctoral Fellow to IBM Almaden for one year). He has also chosen AT&T because of its place near to NYC that was good for his wife's career. As a result since July 2009, I was very happy to have Mihai, a star researcher, as my colleague at AT&T research labs and we talked more about everything during the past years. For example, later I wanted to teach hashing in my Introduction to Algorithms course at UMD; I asked Mihai and he gave me a very good overview about the field including an overview of his recent ground-breaking paper on simple tabulation hashing.


I first knew about Mihai's cancer in Feb 2011. At that time he was taking chemo before a brain surgery in March 2011. Just a day after the surgery he sent an email to David Johnson from the hospital that he already recovered and started thinking about his research problems. After this surgery, doctors, Mihai, and all of us at AT&T were very hopeful that the bad days for Mihai have been passed and Mihai will recover fully and produce lots of papers again:). Indeed everything was fine since then and Mihai even applied for faculty positions in Fall 2011 (he always considered his AT&T (industry) position as a long-term post-doc position). He asked for my opinion about his research statement and I was happy to give him some comments (esp. since I was also a person who first took the path of the industry and then academia). Again everything was fine until mid Jan 2012 that Mihai understood the cancer is back. Unfortunately this time the cancer was very strong and in a week or two he went to a wheelchair from a completely healthy position. I saw him several times at AT&T recently (when I visited there) and I always was very sad to see him on a wheelchair. To my mind, the best good news for Mihai since January 2012 was the fact that Mihai was selected as a co-winner of the 2012 EATCS Presburger Young Scientist Award for his ground-breaking work on data structure lower-bounds. He was very happy about it as he posted in his blog about it as well.


At the end I pray that Mihai's soul rests in peace and the research area of data structure lower-bounds in which he had several ground-breaking works becomes more prosperous due to his work.