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 Ramsey Theory.
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 of interest.
"When it stops having practical applications."
ReplyDeletewhat if it never started having practical applications?
What you have is a simple disagreement with MIP about research taste. In any paper there is the specific content (what results have been proved) versus techniques (models and methods). The specific results of Yao's paper no longer have relevance to data structures but I am sure that MIP would agree that the models defined are still relevant, at least in general cell probe form, and it seems that you believe that the method question of the application of Ramsey theory is still relevant, in that improving the bound would improve techniques in the area. Maybe MIP would ask: given that improving the specific bounds no longer has data structure relevance, isn't there a more motivating example for applying Ramsey theory?
ReplyDelete