[Computational Complexity] Cellprobe complexity- Yao model still relevant?
- 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 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.
Posted By GASARCH to Computational Complexity at 12/01/2008 10:34:00 AM