..mathematics produces the equivalent of one-liners – equations that are pithy, insightful, brilliant. Computer science is more like a novel by Tolstoy: it is messy and infuriatingly complex. But that is exactly what makes it unique and appealing -- computer algorithms are infinitely more capable of capturing nuances of complex reality in a way that pure mathematics cannot.Read the whole interview. I don't know about Einsteins of computer science: arguably we've already seen fundamental tectonic shifts in the way we think about theoryCS. But it is telling that some of the most bedrock developments in algorithms came way before computers were fashionable; the whole of the 70s was a golden era for the study of basic algorithms. It makes this quote seem oh-so-true, and yet tragic, in that we are still trying to make an argument that we've lived and breathed for so many years.
Theoretical computer science would exist even if there were no computers.The more I think about this line, the more I appreciate its deceptive subversiveness. In one line, it turns on its head most of the received understanding about the nature of computer science and the nature of algorithms. How indeed could theoretical computer science exist without computers ? This statement can only make sense once you realize that that the theory of computation is not about computers, but is about the process of computing, about deduction and formal reasoning, and is fundamentally about efficiencies; how quickly, how succintly, how accurately ?
The confluence of computer science and programming has brought our field much riches and much attention, and for that we should be grateful. But it is time for our field to take its rightful place as the language of quantitive and effective science, as Bernard rightly puts it.
(HT: Neighbourhood of Infinity)
Update: Bernard kindly points me to an essay that expands upon the things he says in the interview. It's a freewheeling ride that smacks of crazy guitar riffs and strange rhythms. Don't believe me ? Read it for yourself. Here's a sampler:
Moore's Law has ruled the roost for the last 40 years. All the oohs and aahs you hear about the digital revolution are nothing but the squeals humans emit when tickled pink by Moore's Law. From the nice (medical imaging, e-commerce, whole-genome sequencing) to the vital (Xbox, IM, iPod), its rule has been a veritable ticklefest. Moore's Law has been the sizzling cauldron in which savvy cooks have whipped up a dazzling variety of tasty dishes. Without it, the Information Superhighway would be a back alley to Snoozeville; the coolest thing about a computer would still be the blinking lights.Update II: Lance and Ernie weigh in as well.
Why don't students study computer science? I've begun to see the answer. Despite what everyone says, almost all the jobs you can get with a lowly B.S. in computer science will require some programming, at least at first, if not indefinitely. And hey, despite how much TCS people hate it, programming is pretty fun.
ReplyDeleteGrad school in computer science is so hot right now that most computer science majors get rejected, they expect you to not only have computer science, but probably math as a major. Everyone plays the elitist game where if you didn't go to an undergrad at least as good as the grad school you are applying to, it is doubtful your application will be reviewed. So it really isn't worth planning to study computer science unless you can get into (and want to go to) some 'prestigious' undergrad institution.
And forget it if you are interested in studying science that isn't computer science, like biology or physics, while in computer science graduate school, your application will be quickly rejected.
Do I sound bitter? I am, I'll admit. But also, I think a lot of it comes from talking to many other students who encounter the same problem. Numbers are dropping in computer science because the graduate schools can't support them.
Graduate programs should not require you to TA every year, but most do in computer science. Professors should almost never write papers without their graduate students, but it seems that most do. What is the point of having graduate students if you aren't going to get them involved in your research? I just don't get it, reading SoCG paper announcements, the incredibly low number of papers with any students on them is pretty astonishing. When you are an undergraduate looking at graduate schools, you look at the bigname papers professors you'd be interested in working for have written recently. When a lot of them don't involve their students, you wonder what the point is. You go look at their webpage, they have students. So why aren't they writing bigname papers? Then you go look at papers from a chemistry professor, physics professor, biology professor, etc. and wow, each paper with some great new research in it has a student on it, or maybe two. Sure, there may be a review article here and there written by the prof. And maybe half the papers only have post-docs on them, not students. But if they have students, their papers have students on them.
And sure, CS profs like to say you don't need papers or a postdoc to get a tenure-track job. They'll just call their friends at such and such equivalently ranked institution. Not that citing a comic makes the point any clearer or is a valid source, but I leave you with
http://www.phdcomics.com/comics/archive.php?comicid=680
Posted by anonymous bitter student
Phew! that's a major screed. It sounds like what you're saying is that
ReplyDelete* if you want a job in computer science, you need programming
* if you want to go to grad school, you need far more math and pedigree than is "reasonable", and once you get there, you get overworked, and your profs don't work with you.
I should add that TCS folks don't all hate programming. What we hate is the notion that programming is ALL THERE IS to computer science.
You might find the math requirement for a CS grad degree onerous, but the argument for math is quite solid. Basically if you don't get advanced math training in your undergraduate years, you limit the kinds of programming jobs you can get later on. As outsourcing sends more and more of the basic jobs overseas, a competitive advantage comes from having the right skill set for the next generation of programming jobs, and these involve more math, as Chazelle argues above.
As far as the grad school issues go; It is true that TAing can be a drain on time and can prevent you from getting research done. TAing, if you are allowed to give lectures, does teach you valuable communication skills; skills that many argue scientists despearately need in this day and age.
As for professors not writing papers with their students, I think here you are laboring under a fundamental misunderstanding about how at least theory CS research (since you mention SoCG) works. In a chemistry lab (or in most science labs for that matter), almost all of the heavy lifting is done by students; professors providing direction, guidance and funding. In fact a professor has no time to do significant benchwork on their own because of the sheer labor-intensiveness of the jobs. Hence you'll rarely find professors writing papers without their students.
In more mathematically oriented fields, you might have (say) two grad students working with you, and at least 10 problems you're juggling. If your students can manage all these problems, well and good. If not, often you will be able to produce more than merely what your students come up with (after all, you don't want to prove their theorems for them all the time). So it's hardly student neglect to see theory profs writing papers without students. I'd like to add that since theoryCS is historically underfunded, it is very hard for professors to fund students, and they are accustomed to working alone or with colleagues.
Posted by Suresh
If we drop the ego in TCS, maybe we can be half as good as mathematicians. Case in point "(after all, you don't want to prove their theorems for them all the time)"
ReplyDeletePosted by Anonymous
Anonymous (and anonymous bitter student):
ReplyDeleteI think you have a misunderstanding. How many mathematics papers (witten by people in a pure math department) do you see written by students and professors? I haven't done a large study, but I suspect it is far more rare that in TCS.
As a TCS grad student, I sometimes don't get as much attention from my advisor as I would want, but I am glad he is not working too hard on my problems. If he were to, I am sure he would be able to solve them much quicker than I could. He has read 10 times more papers than I have and has mastered the tricks and techniques of the field. If he shows me a proof for a problem, I learn just as much as reading another paper, but if I discover the trick (maybe with a little help from him) and then apply it successfully, then I am one step closer to mastering it myself.
In order to become knowledgable enough in the field to be able to be a professor myself one day, and in order to establish myself in my field, I need to do my own research. I don't need to have my advisor let me work out some details of his theorems just so I can attach my name to a paper.
Posted by Jeff P
No wonder a theorist want's an "Einstein" for CS, whereas other fields of CS would be happy with progress without Eiffel towers to bow to.
ReplyDeleteanonymous theorist
Posted by Anonymous
Let me first state, that most of my intent is to help TCS understand its problems better, giving you a different perspective, etc. should do nothing but help. I'm sorry if what I write comes off as bitter, angry, confrontational, etc.
ReplyDelete>I should add that TCS folks don't all hate programming. What >we hate is the notion that programming is ALL THERE IS to >computer science.
I agree. But, what the sought-after TCS evangelist will have to learn to say is that while programming is not all there is to computer science, programming certainly has a lot to do with computer science, it is THE real world experience most people have that comes closest to computer science. Replace people with high-schoolers and you will understand that when TCS profs rant against programming, they alienate a lot of potential students who have some experience with programming and computers and would like to turn that into a greater understanding.
>You might find the math requirement for a CS grad degree >onerous, but the argument for math is quite solid. Basically >if you don't get advanced math training in your undergraduate >years, you limit the kinds of programming jobs you can get >later on. As outsourcing sends more and more of the basic jobs >overseas, a competitive advantage comes from having the right >skill set for the next generation of programming jobs, and >these involve more math, as Chazelle argues above.
The argument for math is sound, the argument that grad CS programs should require math dual majors or take math majors before comp sci majors is where the problem lies. Do chemistry graduate schools require physics majors? No. Do they require understanding and a willingness to learn physics principles that apply to chemisty? Yes.
Those next level programming jobs could just as easily involve more business, more accounting, more chemistry, etc. Requiring all of those of every computer science undergraduate would be a bit much, no? Would someone who knew they wanted to make their mark as a business analyst/consultant do better with a CS major and business minor or a business major and CS minor? Should CS serve other programs and fields better, by having more classes at the intermediate, non-programming level?
>As far as the grad school issues go; It is true that TAing can >be a drain on time and can prevent you from getting research >done. TAing, if you are allowed to give lectures, does teach >you valuable communication skills; skills that many argue >scientists despearately need in this day and age.
I've met very few TAs allowed to give lectures. At the largest state schools you may be given a syllabus and a class of students in Intro to [Your Field]. But TAs elsewhere usually have all the responsibilities (like grading) and none of the exciting learning (giving lectures, planning lectures), which admittedly is pretty good to learn at some point.
Also, communication skills could be easily learned by taking english, philosophy, maybe communications/speech classes, where the focus is on presenting the material in writing or word.
>As for professors not writing papers with their students, I >think here you are laboring under a fundamental >misunderstanding about how at least theory CS research (since >you mention SoCG) works. In a chemistry lab (or in most >science labs for that matter), almost all of the heavy lifting >is done by students; professors providing direction, guidance >and funding. In fact a professor has no time to do significant >benchwork on their own because of the sheer >labor-intensiveness of the jobs. Hence you'll rarely find >professors writing papers without their students.
>
>In more mathematically oriented fields, you might have (say) >two grad students working with you, and at least 10 problems >you're juggling. If your students can manage all these >problems, well and good. If not, often you will be able to >produce more than merely what your students come up with >(after all, you don't want to prove their theorems for them >all the time). So it's hardly student neglect to see theory >profs writing papers without students. I'd like to add that >since theoryCS is historically underfunded, it is very hard >for professors to fund students, and they are accustomed to >working alone or with colleagues.
On the last point, agreed, theoryCS needs more funding. This will come hopefully with increased 'evangelism' as Chazelle and others speak for. In fact it looks like it is on its way.
I do understand that many TCS profs do a lot of their own work, juggling 10 different problems at once, rarely consult students, unless perhaps one of the students is given one of their problems as their project. That is completely understandable. I've also heard horror stories from students whose professors have just rewritten their papers entirely without consulting them, before submission (this happens from my friends in biology labs as well). Why are these horror stories? Because learning to write a paper is something a graduate student should be expected to do now. Yes a thesis/dissertation is a paper, but it is not the same. Learning to write/communicate your ideas is very important. This should be done with guidance, obviously, but ideally shouldn't graduate students should be in charge of the writing process by the end of their time in graduate school? This requires that they be in charge of paper-quality research and writing at some point. Maybe I'm wrong, it is not like I'm a professor, but it would certainly seem like students should be involved in this more.
Let me end on two points. First, though I advocate learning lots of stuff, there is a limit. If you spend too much time learning as an undergraduate, and finish three or four majors carefully and honestly, then what, you've spent 5 or 6 years there? Learning as a graduate student could also go down the same road, everytime you run across something you don't know you could take the time to learn everything in that field that seems relevant. This leads to what 10 year PhDs? So you're thirty maybe, looking for a postdoc? Maybe getting tenure before 40?
Also, about the whole needing maths/'prestigious' undergraduate education, I think what bothers me most is that this is never said outright, aloud, to groups of undergraduates considering CS as a field choice and CS grad school as a possibility. I've asked plenty of CS undergrads/dropouts/what have you, and I've heard exactly one person say that they had been told all these things before it was too late. They were the offspring of a professor. I sincerely hope that is not the new requirement for finding out the truth about computer science graduate school, and to an extent undergraduate school. I hope whatever evangelist may come forward to promote TCS at least starts telling potential students what is expected of them, along with the kinds of problems they will be trained to solve and be ready to solve when they graduate (since graduate school isn't for everyone).
that's all.
Posted by anonymous bitter student replies
I feel a bit badly for anonymous bitter student, but I mostly don't get his arguments at all.
ReplyDelete"almost all the jobs you can get with a lowly B.S. in computer science will require some programming, at least at first, if not indefinitely. And hey, despite how much TCS people hate it, programming is pretty fun. "
Not at all true. A BS/BA for computer science is great for business, law school, and consulting, from what I've been told from undergraduates who go into those fields. No programming required -- those doing the choosing are interested in how you think, and people trained in CS generally know how to think logically. I'm imagining that in the near future a CS background will also be completely appropriate for medical school, although currently that's a bit of a stretch.
And as stated before, TCS people don't hate programming. We hate the idea that people think that computer science equals programming.
"Grad school in computer science is so hot right now that most computer science majors get rejected, they expect you to not only have computer science, but probably math as a major. "
I think the competition is always tough for most sciences, at most good schools.
You don't need a great math background to go into computer science generally. But we do expect a strong math background if you're coming in expecting to do theory. Theory requires significant math; if you don't have the background, we're skeptical you can succeed.
The right analogy is not do you need to take chemistry before applying for a physics Ph.D. It's do you need to take quantum mechanics before applying for a physics Ph.D. Generally, yes.
"And forget it if you are interested in studying science that isn't computer science, like biology or physics, while in computer science graduate school, your application will be quickly rejected."
Not at all true. You just have to find an advisor that shares these interests. There are plenty of people working on quantum-related stuff, or computational biology stuff. Try them.
"Graduate programs should not require you to TA every year, but most do in computer science. "
Again, let's be clear -- you seem to be talking about TCS here, not computer science in general. We're not as well funded as we'd like, and that is a bummer. Most students do find some funding and don't necessarily have to TA every year, though you are right, some do. However, for the majority of grad students who are intereted in becoming a professor, if you can't handle TAing every year, I would suggest that's a bad sign. (Professors have to teach all the time too, and while I might object, that's part of the job description.)
"What is the point of having graduate students if you aren't going to get them involved in your research? I just don't get it, reading SoCG paper announcements, the incredibly low number of papers with any students on them is pretty astonishing. When you are an undergraduate looking at graduate schools, you look at the bigname papers professors you'd be interested in working for have written recently. When a lot of them don't involve their students, you wonder what the point is. You go look at their webpage, they have students. So why aren't they writing bigname papers? Then you go look at papers from a chemistry professor, physics professor, biology professor, etc. and wow, each paper with some great new research in it has a student on it, or maybe two. "
As stated before, we do get them involved in research. It's a matter of scale. Students are in training; if they write a couple of big papers (and perhaps a few smaller papers) while in graduate school, that's well above the median. Students are perhaps not yet ready to juggle 10 problems at a time. Professors do.
I also have a different view of biology/physics/chemistry than you seem to. I see lots of papers out of there with 6, 10, dozens of authors, as the whole lab gets their names on a paper, and you can't tell who did anything interesting.
"Also, about the whole needing maths/'prestigious' undergraduate education, I think what bothers me most is that this is never said outright, aloud, to groups of undergraduates considering CS as a field choice and CS grad school as a possibility."
I repeat, for CS in general, you don't necessarily need math. For theory, you generally do, and that's not a big secret as far as I know.
As for needing a prestigious undergrad institution -- well, perhaps you're just not being realistic. Is it necessary? No, but of course it helps. When someone from a top 10 school gets a letter from someone else at a top 10 school saying, "You should take this student," we know what that means. When someone from a school where the professors don't publish say, "You should take this student," we generally need further evidence. Trust me, if we get it, we're happy to find a hidden gem!
Since taking on a graduate student is a substantial risk, I'm not sure there's a great way to change this. Again, I don't think this is particular to CS or TCS in any way. It's the way of the world -- law school, medical school, etc. work similarly. If this is a surprise to you, I'm sorry. Also, there is another solution to this problem -- apply and get in at a less prestigious graduate school, do great work, and people will notice you.
I hope this doesn't put you off. We want people to get into CS in general and TCS in particular. But I just didn't find these arguments particularly persuasive.
Anonymous professor
Posted by Anonymous
For what it's worth, I think Chazelle really overstated his case, by a long shot (and I am a theorist). Where to start? I'll pick a few things that caught my attention.
ReplyDelete"If a math giant from the past –- someone like Gauss –- were to come back to Earth...he would find that math is done much the same way that it was done during his life."
Isn't this partly because math has been around thousands of years longer? If Euclid were to come back, I don't think he would find math done "much the same way it was done during his life." TCS research will eventually stabilize (it already has), and then you can make the same statement about our field.
"For example, mathematics can't come near to describing the complexity of human endeavors in the way that computer science can."
I'm sorry, that is just ridiculous.
"Computer science is more like a novel by Tolstoy: it is messy and infuriatingly complex."
Actually, as far as I'm concerned this is the problem with TCS: most results are obtained through random-looking "tricks" and "tweaks"; what we lack, for the most part, is unification of large bodies of results (I'm thinking here specifically of algorithms) which mathematics has managed to provide.
"Biology, for example, is very quantitatively driven, so a computer science background is imperative."
Another ridiculous statement, as far as I could tell. Not to say that TCS can't be useful for certain types of biology research, but necessary?
"Third...are careers in the field of theoretical computer science."
Is he joking? I wonder what proportion of TCS grad students end up working in a TCS career.
Posted by Anonymous
""And forget it if you are interested in studying science that isn't computer science, like biology or physics, while in computer science graduate school, your application will be quickly rejected."
ReplyDeleteNot at all true. You just have to find an advisor that shares these interests. There are plenty of people working on quantum-related stuff, or computational biology stuff. Try them."
Show me one Computer Science professor who doesn't have a giant disclaimer saying they won't respond to emails before a student is accepted. Pretty hard to 'try them' or convince them you want to study with them if they won't even pretend to be open to talking before you are admitted. Sorry, huge pet peeve of mine. I understand profs have limited time, but really to say "no we won't respond to emails" and then say "try them" seems fairly inconsistent.
Right now, CS admissions looks at every application from a top school. If you went to a mid-ranked or unranked school, and you look absolutely amazing on paper they may look at your application. If your application gets 'pulled' by a friend of a friend, your application is reviewed. Otherwise, forget it. What's wrong with this? The assumption that every student from a top school are worth reviewing while only the best of the best from all the other schools are worth reviewing. Oh, and then if your advisor will call in a favor to one of their friends, they'll yank it and review it. I've confirmed this with several professors at several schools that this is how it works, and I'm sorry, it just isn't fair at all.
And yeah, a lot of the points made by 'Anonymous professor' don't really seem valid, I'm not going to waste my time refuting them because he missed the point of my post (I don't think Suresh did) and tried to just say why I was wrong. You do realize, right, that the world isn't black and white, like in your Theorems? Different views can be helpful, and just trying to say i'm right you're wrong about everything gets old fast, people get bored with the 'discussion' and then you don't have one. Final quote.
"I repeat, for CS in general, you don't necessarily need math. For theory, you generally do, and that's not a big secret as far as I know."
As far as you know, it's not, great. Well, I said it was. And many of my friends said it was. But, here it is, you don't think it was, so you don't want to hear out actual opinions, as students now. Hey, that's fine, you can pretend it isn't a problem. I mean, I was just trying to help, but since "as far as you know" there isn't a problem, then, hey, let's just keep ignoring it. Awesome. I was trying to help, but you (like so many) missed the point, so, I'd rather go back to bed that type anymore. I'm done now.
Posted by quick notes
Reading the posts by anonymous bitter student aka quick notes, it comes to mind that
ReplyDelete(a) you haven't been guided well
(b) your rage over the unfairness of this all appears to have convinced you that the cards are deliberately stacked against you.
What you say about CS profs not responding to email doesn't quite ring true to me, but let's say it is. Different universities have different systems for admitting and funding students, and many univs have a system where a professor has to essentially agree to sign up a student when they come in. Again, this goes back to the issue of funding. if you as a professor make a mistake and choose a student who thinks they want to work in X, but really are not interested or have no talent for X, you've burnt a hole in your meager grant resources.
If a student shows that they "know whereof they speak", then this is less of a problem. But otherwise, risk minimization procedures will involve heurisics like "are they from a good university", "do I know their advisor".
Secondly, if you've done a poll of your friends that suggests that the high level of math content in TCS is a secret, them I'm sorry to say that you (and your friends) have been hopelessly misguided. All you have to do is pick up a proceedings of a conference in TCS, or pick up a journal in the area (which one ? ask a professor, do a google search, find the name of a researcher you might have heard of and look at their papers), and look at what the papers have. I cannot for the life of me understand how in this day and age one cannot discover this fact.
Posted by Suresh
Is it necessary to get a math degree before studying TCS? I don't think so. If one did *well* in "probability" and "linear algebra" (and standard CS courses, of course), he can understand at least half of FOCS/STOC/SODA or SoCG papers.
ReplyDeletePosted by Anonymous
It depends. Probability theory and linear algebra are good all-purpose courses, but you can't avoid needing graph theory as well. You'd probably also need an advanced class in measure theory depending on the kinds of things you want to do.
ReplyDeleteFor computational geometry, a background in topology is becoming ever more useful. In the currently active area of embeddings, functional analysis and fourier analysis are playing a role. If you do quantum computing, then there's lots of complex analysis you'd do well to understand.
I think most importantly though, a training in math gives you a foundation to access newer material that might come up. The topics I mentioned above are areas that are of relevance now. It might be that in the future, other areas become more important, and at that point you need the fundamentals to be able to build an edifice. Hence, a broad-based math curriculum covering algebra, analysis and topology will serve you well.
Posted by Suresh
"Show me one Computer Science professor who doesn't have a giant disclaimer saying they won't respond to emails before a student is accepted. "
ReplyDeleteI think anonymous bitter student might have a point here. I'm pretty sure I've seen Lance write at least once on his blog that he won't respond to students unless they've been admitted.
Posted by Anonymous
Why do you guys limit reality to the computable?
ReplyDeleteTolstoy was a hack. War and Peace is the orignal pathetic soap opera.
I think I might be irritate because my morning coffee wore off.
Posted by Anonymous
quick notes wrote:
ReplyDelete"Not at all true. You just have to find an advisor that shares these interests...Try them."
To which anonymous bitter student responded:
"Show me one Computer Science professor who doesn't have a giant disclaimer saying they won't respond to emails before a student is accepted."
First of all, I don't see what one has to do with the other. I think quick notes was suggesting to find professors who already have interests in fields outside CS, not to try to convince professors to become interested in such things.
Second, I have one of those disclaimers on my website and it is meant to discourage people from sending "spurious" emails (asking to work with me without bothering to see what I work on, or asking for a paid internship even though I have no money for such things). I always respond to a well-written email (by which I mean one which is not a form letter that was clearly emailed to 100 other profs), and would especially be interested in one that showed an attempt to read one of my papers to see what I actually do.
Posted by Anonymous
A converse to the "undergrads should learn math really well" should be "theory grad students should learn implementation issues really well."
ReplyDeleteI spent my undergraduate career studying math, and am a theory grad student now. I know a lot about algorithms and math, but recently realized that I don't know as much as I would like about the nuts and bolts of actually solving real optimization problems on real systems!
I suppose this is fine for a senior theorist, but perhaps your average grad student would be better served with more work on development/numerical computation.
My situation is mostly my fault, but I think others should be wary of this pitfall.
Posted by anonymous theory student
I'm committing applied algorithms blasphemy here, but I can't say that implementation skills are a critical part of a theory student's repertoire. It definitely gives you a much better understand of what algorithms might be considered practical, and this will help a lot if you ever need to work with someone in a different area. But if you're dead set on doing something like complexity theory, then it's not clear to me that implementation skills are something that need to be forced on you.
ReplyDeleteHaving said that, I think it can't hurt, and expands one's horizons :), but it's not the crucial necessity that some math savvy is.
Posted by Suresh
A few random thoughts on various points.
ReplyDelete1) Many professors won't respond to random e-mail from students (outside their univeristy), even students interested in graduate study. Generally I won't. I do agree that most professors will respond to a well-written e-mail, myself included.
Think of it this way. Around application season, I easily get 50+ e-mails from "interested students" (many, admittedly, from foreign countries). I don't have time to read them. I have better uses for my time -- that may sound condescending, and I apologize for that, but that's the truth. (For example, that time could be better spent helping undergraduates from my institution get into graduate schools. Or reading the many dozens of folders of potential graduate students who send in their applications.)
If you want me to read you mail, target it. Mail that begins with "I've read your paper on Balls and Bins, and there seems to be an error on page 7, line 25" will get my attention and start a conversation.
2) The bitter student seems to think professors at top-ranked schools don't read applications from mid-ranked schools. This isn't true in my experience. We review everything here. It is true that a student from a mid-ranked school will have to stand out in order to get noticed. A 4.0 GPA is not enough. Research experience is the best way to get noticed.
3) I enjoyed the comment from the anonymous theory student that theory grad students should learn implementation issues. I fully agree. Especially for students working in algorithms. I still say to whoever will listen (which seems to be very few people) that FOCS/STOC/SODA needs more papers with tables or graphs showing how the algorithms described actually work. (Of course, conversely, other communities, such as networking, might do better with fewer tables and graphs and more analysis.)
Posted by Anonymous
Michaal, I'm assuming that you only want to see tables/charts/ etc for algorithms that are claimed to be relevant in some way ? As David Johnson put it to me the other day, a PTAS is essentially a proof that a lower bound doesn't exist, rather than a really practical algorithm (which an FPTAS might be). In many cases, the algorithm itself is merely a proof of existence (we can break a quadratic bound, we can get to a constant approximation factor) rather than something to be implemented ?
ReplyDeletePosted by Suresh
Suresh,
ReplyDeleteThis leads me to another one of my perhaps unpopular opinions. A PTAS result is (essentially always) a COMPLEXITY result, not an ALGORITHMS result, as some people mistakenly believe. So if you don't want to put a chart/table/etc. in, that's fine. Most COMPLEXITY results don't and shouldn't present data, and a PTAS result is no different.
So yes, I think I agree with your point. If you're claiming that your PTAS is actually algorithmically relevant, then you should be implementing it. If you're just presenting it as a complexity result, there's likely no need.
I would be bothered by papers that imply that such a result (PTAS or similar) is algorithmically relevant without presenting some actual data.
MM
Posted by Michael Mitzenmacher
Michael,
ReplyDeletewhat is the difference between an algorithms result and a complexity result? (I am asking seriously.)
Luca
Posted by Luca
Luca,
ReplyDeleteI understand -- it's a serious question, one I've seen come up on Lance's blog (as I recall, in the arguments regarding the comparison of FOCS/STOC/SODA), without a good answer. I'll first give the standard quip -- it's like pornography, I know it when I see it.
But more concretely, to me, a complexity result answers the question of possibility. Can this be done or can it not be done? An algorithms result provides, as much as possible, an actual solution to an actual problem that (at least ostensibly) someone wants solved. A theory algorithms result provides (as much as possible) proofs or rigorous justification of the algorithm's performance. (A theory algorithms result would also, I would say, include analysis of algorithms already in use as well.)
Ideally, the two inform each other, and certainly there is work that spans both. But as an example, PTAS results, to me, are complexity results. At least until someone implements one and suggests that they are actually worthwhile for a real problem. Any result that is O(n^5) or above is probably a complexity result -- unless it is analyzing an actual algorithm people use, and that's just the best bound people can happen to get.
Indeed, I would guess (though I have not verified) that most "algorithms results" that appear in FOCS/STOC are what I would call complexity results. There's nothing wrong with that -- except for the fact that I, personally, enjoy algorithms more. And that I think part of the reason theory sometimes does not get the appreciation it deserves is because we mistakenly tell people we are doing algorithms when we are actually doing complexity, leaving others to wonder what good we actually are.
Given past experience, I await being chastised for suggesting this differentiation.
Posted by Michael Mitzenmacher
It's an interesting distinction. I think it's useful not for practising theoreticians necessarily, but for non-theoreticians. As Michael points out, we have done ourselves no favors by claiming that algorithms are "efficient" when we merely mean "polytime". Refining the term "algorithm" to imply "practical" has its merits, and personally I'd love to think that some times I am actually doing complexity :).
ReplyDeleteWhat follows as a consequence though (and this is not surprising since Michael has expressed opinions on this before) is that many of the algorithm presented in FOCS/STOC/SODA lose a good amount of their validity. As complexity results they are often uninteresting: maybe they shave off a tiny constant somewhere, or maybe they solve some special case variant of a problem. But as algorithms they are often useless, because they use techniques that lie in the realm of complexity i.e are not at all practical.
A careful distinction between complexity and algorithms in terms of their governing purpose might make a lot of (old-style) algorithms work quite pointless. And maybe this was Michael's intention all along ;)
Posted by Suresh
I know this is a years-old conversation, but I thought I'd chip in. Mathematical background is the only way to access new tools and techniques - algebraic topology, functional analysis, equivariant topology, Riemmanian manifolds. I'd guess many professors might even struggle to acquire that much machinery independently, let alone grad students. So good coursework helps a great great deal.
ReplyDeleteI do think more students contribute to SoCG papers than might be imagined, and that one can get by without much math background in areas involving discrete algorithms and point sets. I can't generalize extensively- but Nabil Mustafa, for example had two students work with him as coauthors on his paper in SoCG this year. (Both of whom, by the way, didn't have a strong math foundation). There is always room for students to tackle interesting problems, especially the ones requiring little machinery.
The major problem most students face, is the lack of "name" recommendations - many talented, deserving students lose out for not having such backing, and I have every sympathy for their right to feel aggrieved by such.