tag:blogger.com,1999:blog-3722233.post114592946909381771..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Theory and SystemsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger35125tag:blogger.com,1999:blog-3722233.post-1146166564655019182006-04-27T14:36:00.000-05:002006-04-27T14:36:00.000-05:00I think part of the objection here is that complex...I think part of the objection here is that complexity theory is universally lumped into CS. It could just as easily be lumped into math. But either way it is sort of on the edge. So if you're into complexity theory, other requirements are going to feel all-in-one-direction where ever you are. A similar situation happens with some areas of logic - they other get forced into philosophy or math, when really on the edge of both.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146161747639661512006-04-27T13:15:00.000-05:002006-04-27T13:15:00.000-05:00Because systems is (obviously) a key part of compu...Because systems is (obviously) a key part of computer science, and if you are going to get a computer science Ph.D you should be able to demonstrate a reasonable knowledge in all the main areas of computer science.<BR/><BR/>If you don't want to take systems or AI courses you should seek a degree in some other discipline (e.g Math).<BR/><BR/>I think it is as simple as that, regardless of whether they are pedagogical benefits or not(sometimes there are, sometimes there aren't).<BR/><BR/>OTOH the European model is a bit different, it would be intersting to see what differences can be attributed to these different educational styles.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146103359962233842006-04-26T21:02:00.000-05:002006-04-26T21:02:00.000-05:00I'm graduating senior with hopes to one day get my...I'm graduating senior with hopes to one day get my PhD in Theory. Right now I'm working on a copiler project that is anything but interesting, so I can relate to the issue. However, I've got to admit that some of the programming intensive courses I've taken in the past have been positive, in retrospective. Nonetheless, I rather prove theorems than code in C any day of the week, and twice on Sundays.alhttps://www.blogger.com/profile/02786293905055015034noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146100296691862992006-04-26T20:11:00.000-05:002006-04-26T20:11:00.000-05:00--- Piotr,can you expand on your comment? Is the i...<EM> --- Piotr,<BR/>can you expand on your comment? Is the impact of streaming algorithms etc. on systems concrete or potential, present or possibly future?</EM><BR/><BR/>Sure. <BR/><BR/>I think it is fair to say that streaming algorithms had a significant impact on academic/industrial systems research. For example, in 2002, a tutorial on data stream algorithms was given at three main database/data mining conferences, namely SIGMOD, VLDB and KDD. Every year each of this conferences has one or more sessions dedicated to this topic. Streaming algorithms is a topic also present at networking conferences.<BR/><BR/>As far as concrete systems go, my knowledge here is somewhat limited. Nevertheless, two examples that I am aware of are Gigascope and Scalable Traffic Analysis Service, both developed at AT&T. <BR/><BR/>(additions/corrections welcome)<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146085028330566592006-04-26T15:57:00.000-05:002006-04-26T15:57:00.000-05:00Clearly systems students should take theory course...<EM>Clearly systems students should take theory courses, it's probably the only time these poor saps get to do something intellectually challenging!</EM><BR/><BR/>Not a very nice thing to say, isn't it? I've taken both theory and systems courses, and aside from a small number of key insights, most of the work in theory is just symbol pushing. Now the same can be said of systems too, if you replace "symbol pushing" by "programming" or "implementation".<BR/><BR/>If you find symbol pushing "intellectually challenging", then unfortunately you belong to the class of "also-ran" theoreticians.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146082433415503612006-04-26T15:13:00.000-05:002006-04-26T15:13:00.000-05:00Luca: We want systems students to take theory cour...Luca:<BR/><BR/><I> We want systems students to take theory courses</I><BR/><BR/>Clearly systems students should take theory courses, it's probably the only time these poor saps get to do something intellectually challenging!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146079230048025682006-04-26T14:20:00.000-05:002006-04-26T14:20:00.000-05:00programming is a wastejust use copy pasteIf no-one...<EM><BR/>programming is a waste<BR/>just use copy paste<BR/></EM><BR/><BR/>If no-one programmed, then what would you copy and paste from?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146072635442413432006-04-26T12:30:00.000-05:002006-04-26T12:30:00.000-05:00programming is a wastejust use copy pasteprogramming is a waste<BR/>just use copy pasteAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146067327422547472006-04-26T11:02:00.000-05:002006-04-26T11:02:00.000-05:00�Getting a Ph.D. in theoretical computer science i...�Getting a Ph.D. in theoretical computer science is as big a self-indulgance as going to Art school. Would you have any sympathy to an art student who complains that he has to take too many graphics design classes?�<BR/><BR/>Yes. Your appreciation for beauty is dubious at best. I suggest you take an art course wherever you are. (Most universities offer them.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146064873495315602006-04-26T10:21:00.000-05:002006-04-26T10:21:00.000-05:00Getting a Ph.D. in theoretical computer science is...Getting a Ph.D. in theoretical computer science is as big a self-indulgance as going to Art school. Would you have any sympathy to an art student who complains that he has to take too many graphics design classes?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146063541124079492006-04-26T09:59:00.000-05:002006-04-26T09:59:00.000-05:00The synergy of theory and systems must not be disc...The synergy of theory and systems must not be discounted. There are cases where some very elegant theory has given rise to some well-engineered systems (see the ML programming language, for instance). <BR/><BR/>Take a look at the founding fathers and the leading lights of CS, and you will immediately see that all of them did excellent theoretical work, and excellent systems building.<BR/><BR/>It is only the also-ran theoreticians (read losers) that complain about having to do systems work (and the same comment also applied to also-ran systems builders)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146062628435885662006-04-26T09:43:00.000-05:002006-04-26T09:43:00.000-05:00Sure there's a benefit to having a broad exposure ...Sure there's a benefit to having a broad exposure to computer science, but forcing it on *everyone* in CS seems to me like the current version of liberal arts in undergraduate education, where mind-broadening courses morph into requirements. I think it's clear that there's no clear solution: some CS PhDs might thrive learning about other CS subfields, while for others it is a waste of time. <BR/><BR/>The one set of course requirements that might be useful to help students' careers: software engineering and computational finance!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146062369817088832006-04-26T09:39:00.000-05:002006-04-26T09:39:00.000-05:00I haven't started my systems work yet, and I am dr...<I>I haven't started my systems work yet, and I am dreading it...</I><BR/><BR/>Then there seems to be little point to the rest of your post since you don't know what you are talking about. What you describe might apply to current computer architecture but is way off base when discussing OS, networking, embedded systems or VLSI. In all of the latter areas there are significant issues that raise clear theoretical problems. As a theory grad student I found my required OS and VLSI courses to be among the most fascinating I took (even counting my theory courses). <BR/><BR/>I will say that most theoreticians would do well to avoid computer architecture courses as they are currently constituted. It seems that, unlike OS, there is a mindset in those courses that is antithetical to a theoretical way of thinking. There are interesting places where theory and architecture meet (cf. the SPAA conference) but almost nothing of that makes its way into current curricula.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146040779748476712006-04-26T03:39:00.000-05:002006-04-26T03:39:00.000-05:00I haven't started my systems work yet, and I am dr...I haven't started my systems work yet, and I am dreading it...<BR/><BR/>I guess I would posit the following analogy:<BR/><BR/>theoretical cs - physics<BR/>systems - engineering<BR/>operating system - internal combustion engine<BR/><BR/>While there are clearly important theoretical questions (such as thermodynamics?) that arise from building an internal combustion engine, it is not something that is worth the average physicist's time. I would agree that we should be _in communication_ with systems people, but it is very unclear to me why I personally should have to build a kernel or some other large piece of an operating system. No physics grad school would have you sit down for a quarter and build an internal combustion engine in the machine shop. Understanding the theoretical questions (such as caching algorithms or whatnot) that arise from systems work is good, as is a theoretical framework in which to address them.<BR/><BR/>Learning how to program fairly large projects, should that ever come in handy, would be analogous to the physicists having to learn how to design an experiment, which is fine. But I don't think there is much that competes in size and complexity with an operating system that I could use my OS knowledge for. I think it is clear that the sort of rough-and-ready code we throw together to do experiments with is a very different sort of thing than an enormous system that could easily be adapted to commercial use, just as a physics experiment is different from designing an airplane.<BR/><BR/>-one of Lance's studentsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146030169566066432006-04-26T00:42:00.000-05:002006-04-26T00:42:00.000-05:00Programming and "Systems" are not the same thing! ...Programming and "Systems" are not the same thing! Everyone in the world (not just CSers) should know something about computer programming, but this is a separate issue.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146023537642384092006-04-25T22:52:00.000-05:002006-04-25T22:52:00.000-05:00Piotr,can you expand on your comment? Is the impac...Piotr,<BR/>can you expand on your comment? Is the impact of streaming algorithms etc. on systems concrete or potential, present or possibly future?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146017963684486502006-04-25T21:19:00.000-05:002006-04-25T21:19:00.000-05:00A few examples, of theory work having impact in sy...A few examples, of theory work having impact in systems: streaming algorithms, Tornado codes and relatives, network coding.<BR/><BR/>(and I am sure I forgot something)<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146011491123437212006-04-25T19:31:00.000-05:002006-04-25T19:31:00.000-05:00Some very good theoretical work has arisen from qu...<I>Some very good theoretical work has arisen from questions from the systems community and vice versa.</I><BR/><BR/>What would be good examples for the vice versa part, in fields other than Programming languages?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146009547729301092006-04-25T18:59:00.000-05:002006-04-25T18:59:00.000-05:00I did my Ph.D. in algorithms, and even though my w...I did my Ph.D. in algorithms, and even though my work was theoretical, I benefited greatly from having an application-driven topic, at least financially. <BR/><BR/>I'd say that if one must take "applied" courses as a theory grad student, they should be at least driven by those applications for which there are sponsors with deep pockets. For example, most theory grad students would be better off taking bioinformatics classes rather than systems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146003032610340842006-04-25T17:10:00.000-05:002006-04-25T17:10:00.000-05:00"Just like theoretical physicists should do some e..."Just like theoretical physicists should do some experimental physics to realize what they do should have some grounding in reality"<BR/><BR/>Physics is a science and thus has to be grounded in reality. Computational theory is mathematics as was pointed out by other commenters. There's little point in trying to ground ourselves in reality (I'd say that it is reality), and I can't see how programming an operating system will give us any special insight into algorithms when we are concerned with asymptotics. O(n^3) algorithms seem to take a long time in practice.<BR/><BR/>That said, there's nothing wrong with taking OS, and there is always the off chance that it could be the source of some inspiration in Theory. As a graduate student I'm on the objecting side of having it be required though. I'm fine with being required to know how to program, and to understand data structures. Beyond that I say that systems courses should be optional and perhaps fulfill some distributional requirement.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1146001422085869092006-04-25T16:43:00.000-05:002006-04-25T16:43:00.000-05:00As a Berkeley AI grad student, I naturally know pl...As a Berkeley AI grad student, I naturally know plenty of other AI students. I've never known any of them to complain about having to take theory or systems breadth/distribution courses. In fact, several are minoring in theory/systems (e.g. electing to take significantly more courses in these areas than is minimally required).<BR/><BR/>As for the anonymous who questioned the American practice of a graduate coursework component: I think that this system works well provided that the institution in question has enough resources/interest to offer relevant, advanced coursework.<BR/><BR/>Students in the British-style postgraduate program tend not to get the same structured introduction to important but sophisticated material. They are left to their own devices (which can work out, but doesn't always).<BR/><BR/>Just because the American format tends to add 2 years to the (British-type) duration of the doctoral program doesn't mean that grad students here don't do seriously great research during their first 2 years of grad school! It isn't wasted research time. Graduate-level coursework also tends to involve a short-term research project, which encourages trying out different research areas and helps students hook up with appropriate advisors (e.g. course instructors). A further benefit (if I haven't listed enough already), coursework helps forge student-student bonds, both in the social and academic/research sense. <BR/><BR/>Representing the system as "keeping them [students] enslaved as long as possible" is unfair. A research grad/postgrad program, anywhere, provides the student with many benefits -- a valuable educational experience, a research apprenticeship, and a qualification (that opens doors to following an interesting career and in some cases making more money)! Sure, the university and advisor get something in return -- a cheap TA, a research assistant, etc. but why shouldn't they?? Students usually get paid to earn their degree, while helping out in return (and the act of teaching/research assistanting provides valuable experience too).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145994408660627562006-04-25T14:46:00.000-05:002006-04-25T14:46:00.000-05:00[...]that of regarding complexity theory as a subf...<EM> [...]that of regarding complexity theory as a subfield of computer science.<BR/><BR/>Computational Complexity Theory is, scientifically speaking, a branch of *mathematics*. <BR/></EM><BR/><BR/>I dont see why the above statements cannot be both true. Complexity theory, or TOC in general, is a pretty rich area, influenced by both mathematics and computer science (and other fields as well, e.g., quantum physics).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145980901739735432006-04-25T11:01:00.000-05:002006-04-25T11:01:00.000-05:00Hear hear! (re: Luca's comment)We can't expect sys...Hear hear! (re: Luca's comment)<BR/><BR/>We can't expect systems to respect theory, if we don't respect systems. If you really think that your systems courses are a waste of time (I don't), then at least do it because you cringe when systems people say things like "NP-complete algorithm". Call it a sacrifice for the greater good.<BR/><BR/>-ryan williamsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145979860005019852006-04-25T10:44:00.000-05:002006-04-25T10:44:00.000-05:00Yeah, I know plenty of fellow non-theory grad stud...Yeah, I know plenty of fellow non-theory grad students who wonder why they have to take theory courses. "They're too hard and we'll never use it," they say. Knowing how to argue that an algorithm is correct or that a problem is NP-Hard is invaluable in systems and AI, in my opinion.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1145978188727422812006-04-25T10:16:00.000-05:002006-04-25T10:16:00.000-05:00There is also one more reason:- We want systems st...There is also one more reason:<BR/><BR/>- We want systems students to take theory coursesLucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.com