Some sad news, complexity theorist Ingo Wegener passed away last
Wednesday at the age of 57. We will have a proper obituary soon.
My last post LINK asked a question about
Yao's paper. MIP said (essentially) that since there
are more realisitic models of data structures for membership,
and very good (better than binary search) algorithms,
by now, there is nothing interesting in Yao's paper
for computer science, just for people passionate about
That raises a few questions:
When is a problem no longer interesting?
When it stops having practical applications.
If we take this answer then
large parts of math and even TCS have stopped
being interesting. (Maybe this is true.)
When it stops being relevant to the problem it was
intended to solve. This fit Yao's paper.
But other branches of math are far removed
from the problem they were first deveoloped to solve.
For one example,
computability theory seems far removed from
questions in the foundations of math.
But is it still interesting?
However, I still want to know the answer to my question.
Its mostly been answered, but not completely.
(The paper IMPLICITY O(1) PROBE SERACH by Fiat and Naor, SICOMP Vol 22, 1993
has better bounds for some cases, but not quite for the one I
had in mind.)
So, only of interest to
people passionate about Ramsey Theory.
Actually, I doubt Ronald Graham cares about the problem.
Might be more correct to say
people passionate about applications of Ramsey Theory.
Are there such
people? Are there people who have
websites dedicated to applications of Ramsey Theory?
Are there papers on
Ramsey Theory Applications?
Perhaps there are, and to the authors the question may still be
Posted By GASARCH to Computational Complexity
at 12/01/2008 10:34:00 AM