tag:blogger.com,1999:blog-3722233.post4676111875248523694..comments2021-02-28T13:36:16.682-06:00Comments on Computational Complexity: The Time of ResearchLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-45582999835247885992012-09-18T19:43:27.341-05:002012-09-18T19:43:27.341-05:00I think this depends crucially on how one defines ...I think this depends crucially on how one defines relevancy. Previous experience in mathematics graduate school exposed me to an ongoing debate raging between purists and applied scientists. More extreme elements in either camp refused to validate the other, a rather destructive perspective.<br /><br />G.H. Hardy in A Mathematician's Apology proudly boasted that prime number theory, a favorite of his, bore absolutely no application. Yet now it provides a foundation for modern cryptography. Archimedes didn't dream up the exhaustion principle for the sake of some application; rather, he enjoyed solving problems. Yet this limiting procedure underwrites calculus.<br /><br />Hardy (and likely Archimedes would have) agreed that pure mathematics holds timeless appeal in part because it is enjoyable. Whether your threshold of enjoyment is tic-tac-toe or computing free resolutions, you're playing with the purists.<br /><br />I feel that a healthy perspective is to recognize that pure and applied mathematics are complementary, and that both are essential for the progress of civilization.NP Slaglehttps://www.blogger.com/profile/06322388966706601689noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73711067408861706222012-09-15T20:46:00.933-05:002012-09-15T20:46:00.933-05:00The difference is not that theory results remain t...The difference is not that theory results remain true while systems results become false. The difference is that in theory most people don't care much about the relevance of their results to applications and industry so in one sense most theory results are irrelevant even at the time they were discovered and remain so. On the other hand system people care about applications in the industry a lot, their results are expected to be relevant at the point of their discovery but can become irrelevant with later advances.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65649858492096633102012-09-09T08:39:35.278-05:002012-09-09T08:39:35.278-05:00I completely agree the journals are TCS are very i...I completely agree the journals are TCS are very important.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11266986647795886682012-09-08T01:46:38.643-05:002012-09-08T01:46:38.643-05:00As a systems person, the reason I publish mainly i...As a systems person, the reason I publish mainly in conferences is simpler: the conference venues are higher quality and are the central venues for the community.<br /><br />Also, the top conferences are rigorous in their reviewing, so there is often only a modest difference in how "archival" a top systems conference paper is, compared with a journal version.<br /><br />Conferences are also not that much faster, when you account for the chance of rejection and time to wait for the next deadline.Brighten Godfreyhttp://www.cs.illinois.edu/~pbg/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63811102398996326472012-09-07T13:33:33.377-05:002012-09-07T13:33:33.377-05:00Some journals (including at least one ACM journal)...<i>Some journals (including at least one ACM journal) disallow any submission that contains substantial content that has previously appeared, e.g., in a conference paper. Some (including the mentioned ACM journal) even disallow submissions for which the main result or conclusion has appeared in a press release.</i><br /><br />This isn't true of any publications where theory papers appear as far as I know. What journal is it?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66916269763739501392012-09-07T07:25:56.979-05:002012-09-07T07:25:56.979-05:00Let T be a theorem. Let t_0 be the time of first p...Let T be a theorem. Let t_0 be the time of first publication of T. For any t > t_0, let f(t;T) be the no. of new theorems that were proved with the help of T in the time interval (t_0, t]. For sufficiently large t (say t - t_0 = 50 years), f(t;T) is a measure of how productive T has been to mathematicians. <br /><br /><br />Let k be the average of f(t;T) over all theorems that have appeared in FOCS/STOC. Is k > 1? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49425578118721068992012-09-06T22:19:44.662-05:002012-09-06T22:19:44.662-05:00Your comparison between systems and theory seems a...Your comparison between systems and theory seems a bit one-sided. Sure, a theorem is always true, but can become irrelevant. (If you prove a consequence of some assumed separation, and the separation is later shown to be false, the first result is no longer interesting.) But in systems, a system that works at one point in time will work forever, though it may only run on outdated hardware or solve a problem that no longer exists. What is the difference, exactly?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89257986254478691452012-09-06T10:59:28.010-05:002012-09-06T10:59:28.010-05:00I wonder if the systems person is right. At a min...I wonder if the systems person is right. At a minimum, well-written journal papers allow future researchers to explore the history of ideas in systems research, just as I had to read about the first stack machine for my architecture class. But even more, it seems to me (from my very limited perspective on systems) that systems returns to some of the same sets of ideas again and again (just as computing power has shifted from servers to clients and back towards servers in my lifetime, and the ability to handle all the data in memory was possible only during a brief interval), only with different types of tradeoffs possible each time. It might be useful to have these ideas well-documented rather than require future generations to rediscover them. David P. Williamsonhttp://www.davidpwilliamson.net/worknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64433917998016707062012-09-06T10:15:01.901-05:002012-09-06T10:15:01.901-05:00Some journals (including at least one ACM journal)...Some journals (including at least one ACM journal) disallow any submission that contains substantial content that has previously appeared, e.g., in a conference paper. Some (including the mentioned ACM journal) even disallow submissions for which the main result or conclusion has appeared in a press release. To me this seems completely opposed to the purpose of a refereed archival journal. It places the author(s) in the position of having to choose between timely dissemination and archival status. I wonder at this point in time whether the latter is even meaningful.Anonymousnoreply@blogger.com