One of the comments on
this blog pointed out correctly that for a theorem
to be accepted by the community is not a Eureka Moment.
It is a social process. The author of the comment was probably alluding
to an excellent article by DeMillo and Lipton that I blogged
about
here.
I highly recommend reading the article that blog points to.
We often say or write things like

In 1978 Yao proved that if you store n elements of U in a table of size
n then (for large U) membership requires log n probes (Ref FOCS 78).

In 1981 Yao proved that if you store n elements of U in a table of size
n then (for large U) membership requires log n probes (Ref JACM 81).
Personally I try to include both the conference and the journal version
in a citation. That solves the citation problem.
However, what does
prove mean? It could be that Yao proved this
in 1977. The exact time/day/year when something is proved is not
that well defined. The original post was about the Fund Lemma
where the paper was written in 2004 and accepted in 2009.
What was its status in 2006? Proven or unproven?
Is there a better way to say these things?

In his FOCS 1978 paper (see also Journal version in JACM 1981)
Yao proved the following:

In his JACM 1981 paper (original in conference version in FOCS 1978)
Yao proved the following:
These both sound awkward. I am willing to live with using
proved even though its not quite right.
Does someone have an alternative?
Was Time Magazine right to say that the Fund Lemma was one of
the big Science Stories of 2009 even though the paper was
written in 2004? I think so acceptance in a journal
seems like a good time to declare YES THIS IS TRUE.
And I do not know an alternative.

Posted By GASARCH to
Computational Complexity at 1/25/2010 09:04:00 AM