tag:blogger.com,1999:blog-3722233.post116978290575454956..comments2024-02-27T13:05:20.652-06:00Comments on Computational Complexity: Too Useful to be a Computer ScientistLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-1170071117654737412007-01-29T05:45:00.000-06:002007-01-29T05:45:00.000-06:00Paul Beame sez: ``Why not go for the trifecta: mat...<I>Paul Beame sez:</I> ``Why not go for the trifecta: mathematician, physicist, and computer scientist? I can think of one - John von Neumann.''<BR/><BR/>John von Neumann was an engineer. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1170060506679740512007-01-29T02:48:00.000-06:002007-01-29T02:48:00.000-06:00#17 obviously did not get the joke in #16's post.....#17 obviously did not get the joke in #16's post...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1170035414959350152007-01-28T19:50:00.000-06:002007-01-28T19:50:00.000-06:00Lance, your on-line Short History of Complexity Th...Lance, your on-line <A HREF="http://people.cs.uchicago.edu/~fortnow/papers/history.pdf" REL="nofollow">Short History of Complexity Theory</A> (with Steve Homer) is IMHO an excellent summary of the rich roots of the field.<BR/><BR/>Near the end you and Steve say "We know surprisingly little about the computational complexity of quantum computing." It's been five years ... if you have any new remarks or insights in this regard, well, I for one would be an attentive and appreciative reader!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1170023138312787082007-01-28T16:25:00.000-06:002007-01-28T16:25:00.000-06:00Hmm, but what exactly makes the difference? The me...Hmm, but what exactly makes the difference? The methods you use or the field you apply them to? Do we really care?<BR/><BR/>Put differently: Is the difference between a software engineering person and a theoretical computer scientist working on algorithms larger or smaller than the difference between either one to a mathematician?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169953582606143162007-01-27T21:06:00.000-06:002007-01-27T21:06:00.000-06:00John von Neumann had a PhD in mathematics and held...John von Neumann had a PhD in mathematics and held a math professorship all his life. Most of his papers were in math or applied math. He just happened to do world class physics, computer science and economics on the side.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169940225687178082007-01-27T17:23:00.000-06:002007-01-27T17:23:00.000-06:00John von Neumann was a physicist.John von Neumann was a physicist.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169930015000756602007-01-27T14:33:00.000-06:002007-01-27T14:33:00.000-06:00Why not go for the trifecta: mathematician, physic...Why not go for the trifecta: mathematician, physicist, and computer scientist? I can think of one - John von Neumann - who certainly fits the bill.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169878998885199642007-01-27T00:23:00.000-06:002007-01-27T00:23:00.000-06:00Once physicists have done something computer scie...Once physicists have done something computer scientists care about they cease to be physicists and are now computer scientists. John Atanasoff for example.Chad Brewbakerhttps://www.blogger.com/profile/10443154815748267611noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169873076622289072007-01-26T22:44:00.000-06:002007-01-26T22:44:00.000-06:00regarding a posters contention that TCS is a subfi...regarding a posters contention that TCS is a subfield of math, I think what we call theoretical computer science is a union of two different fields. one is a theory <I>of</I> computer science (which is not mathematics, though mathematical in nature), and the other is mathematics of turing machines.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169860983023724732007-01-26T19:23:00.000-06:002007-01-26T19:23:00.000-06:00a self-fulfilling prophecya self-fulfilling prophecyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169853700006836762007-01-26T17:21:00.000-06:002007-01-26T17:21:00.000-06:00How about this definition: You're a physicist if ...How about this definition: You're a physicist if you can teach the physics undergrad courses through quantum mechanics. You're a mathematician if you can teach the first undergrad course in abstract algebra or real analysis. What would the analog for computer science be, anyone? Or is the field too diverse, and do we have to define computer scientists by subfields? <BR/><BR/>Anyway, if you get a PhD in a interdisciplinary area like quantum computing, you should at least learn enough of one of the disciplines to teach the basic courses in that field. Otherwise, you may have difficulty getting an academic job.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169852296913375072007-01-26T16:58:00.000-06:002007-01-26T16:58:00.000-06:00What do you mean by "If we want computer science t...What do you mean by "<I>If we want computer science to continue to prosper we need to continue to reach out to other fields and do our best to make them understand the role computer science can play in helping understand their basic questions.</I>"<BR/><BR/>Do you mean that we have to solve their basic questions for them? That's really, really tough. It might even be easier to solve our basic questions (P =? NP, anyone?). <BR/><BR/>Or do we have to collaborate with a physicist and help him use computer science to solve his questions? That's easier, but it's still pretty hard. You have to identify a physicist who's willing to collaborate, talk to each other long enough to start speaking each other's languages, find a physics question which computer science techniques can be fruitfully applied to, and help solve it. This can be really worthwhile, but good opportunities for this kind of collaboration don't come up very often.<BR/><BR/>Or maybe you mean that we should go down the hall to the physics department, grab one of the professors there by the collar, and tell him: "Look, you idiots. You could get a lot of mileage out of theoretical computer science techniques. You should learn them." <BR/><BR/>This last technique is not guaranteed to make friends. Think how theoretical computer scientists react when a mathematician or physicist says that proving P != NP will be easy with their techniques. (I've seen this happen several times, although mathematicians respect this problem a lot more since it became worth a million dollars.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169846157454284582007-01-26T15:15:00.000-06:002007-01-26T15:15:00.000-06:00As a once-upon-a-time student of AI, this also rem...As a once-upon-a-time student of AI, this also reminds me of what AI faced. Solve a problem, and it obviously wasn't AI in the first place. Maybe we needed more physicists!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169844717232929072007-01-26T14:51:00.000-06:002007-01-26T14:51:00.000-06:00Oh no, not another of those set separation questio...Oh no, not another of those set separation questions!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169834205493414472007-01-26T11:56:00.000-06:002007-01-26T11:56:00.000-06:00Scott you forgot the most famous computer scientis...Scott you forgot the most famous computer scientist in all of physics: Richard Feynman!Dave Baconhttps://www.blogger.com/profile/03506030153326411733noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169828956114149472007-01-26T10:29:00.000-06:002007-01-26T10:29:00.000-06:00This is a general property of physicists, at least...This is a general property of physicists, at least the condensed matter version of them. To them anything useful is part of their branch of physics and useless things are not.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169828832610746292007-01-26T10:27:00.000-06:002007-01-26T10:27:00.000-06:00>Same thing happens with Mathematicians. >I've had...>Same thing happens with Mathematicians. >I've had almost the same conversation about >Agrawal, Kayal and Saxena.<BR/><BR/>The situation is perhaps different with mathematics than with other fields such as physics, economics or biology.<BR/>Indeed, one can argue that in addition to being a subfield of computer science, theoretical computer science is also a subfield of mathematics.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169806699434402012007-01-26T04:18:00.000-06:002007-01-26T04:18:00.000-06:00Not only is Peter Shor a computer scientist, so we...Not only is Peter Shor a computer scientist, so were David Deutsch and John Bell.<BR/><BR/>The best defense is a good offense.Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169790986677200732007-01-25T23:56:00.000-06:002007-01-25T23:56:00.000-06:00You mean "This view has changed a qbit"!You mean <BR/>"This view has changed a qbit"!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169790181963525812007-01-25T23:43:00.000-06:002007-01-25T23:43:00.000-06:00I thought Peter Shor was a mathematician! :)Any ph...I thought Peter Shor was a mathematician! :)<BR/><BR/>Any physicist who says computer scientists have done nothing for quantum computing certainly doesn't work in the field. <BR/><BR/>And at some point the distinction between physicist and computer scientist begins to vanish in quantum computing. What am I? I've published in Physical Review Letters, STOC, Nature, and SODA. Am I a computer scientist or a physicist? At some point the label just stops mattering except for telling jokes.Dave Baconhttps://www.blogger.com/profile/03506030153326411733noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169786837300107892007-01-25T22:47:00.000-06:002007-01-25T22:47:00.000-06:00Same thing happens with Mathematicians. I've had a...Same thing happens with Mathematicians. I've had almost the same conversation about Agrawal, Kayal and Saxena.Anonymousnoreply@blogger.com