Monday, April 24, 2006

Theory and Systems

An anonymous graduate student asks
Why do theory students have to take systems courses?
Most American Ph.D. programs have distributions requirements where every student must take courses and/or exams in many different subfields of computer science. Why have these distribution requirements and in particular why should theory students need to know systems concepts they feel they will never use.
  • If a student becomes an academic computer scientist they will have to evaluate systems candidates for hiring and tenure and better they can tell the difference between good systems and bad systems.
  • Just like theoretical physicists should do some experimental physics to realize what they do should have some grounding in reality, all computer scientists should do some programming to get a better feeling about the concept of computation.
    The mission of computational complexity is to understand the power of efficient computation and how can one really understand efficient computation if they don't try to do it themselves.
  • A good systems class will surprise many theory students by showing that much of systems have a strong theoretical underpinning and basic concepts like abstraction underlies both theory and systems. Some very good theoretical work has arisen from questions from the systems community and vice versa.
Many new Ph.D. students make the mistake of trying to fulfill all of their distribution requirements as soon as possible. But this makes the beginning of the Ph.D. program feel like an extension of undergraduate education. Better to take the courses over time and get involved in research as soon as possible.

I did receive my Ph.D. in Applied Mathematics and didn't have a systems requirement. But I did take systems classes as an undergrad and during my first year at Berkeley and I did extensive programming in high school and during my undergrad days. Programming has helped me tremendously in my research. Putting together old theorems to make new theorems is not unlike making different pieces of code work together.

One might also ask why theory students should take AI courses? I'll leave that to a future post.


  1. This is a very nice post. Especially last point of saying equivalence between coming up with new theorems and engineering software is very neat and motivates people to understand the significance of different kinds of efforts people put in Computer Science.

  2. I agree that this was a nice post, although it was clearly written from the "complexity" point of view. For people who want to work on "algorithms", I think the case is even clearer why you want to take systems courses. In the long run, your algorithmic questions are going to have to come from somewhere, so you'd best be able to talk to and understand the problems of one or more systems communities -- especially if you hope to have an impact on the "real world" in your lifetime.

    One of the things I appreciate about my education at Berkeley is that I was forced to take many systems courses. They weren't always enjoyable -- I'll admit, some seemed a complete waste -- but overall I do think they made me a better, more well-rounded computer scientist.

    Now that I've clearly expressed my bias, I must admit that I find the fact that a computer science theory graduate student -- even one in complexity -- would ask such a question both sad and disturbing. It's times like this when I understand why theory as a whole gets asked about its relevance to CS generally or gets labelled as arrogant.

    My advice to the graduate students -- if you are getting a Ph.D. in computer science, you should learn something about the field other than just your own immediate more theoretical interests. Some breadth as well as depth is a very good thing.

  3. Maybe a better question is, why should theory students with an undergraduate degree in CS take graduate-level systems classes designed for students intending to do research in those areas?

  4. "how can one really understand efficient computation if they don't try to do it themselves"

    Why don't electrons develop a theory of atmoic physics?

    Systems can be underwhelming at times because it often isn't philosophically well-motivated. There's not enough creativity. Of course there are exceptions, Stroustrup for instance...

  5. Hell, it might also help if you knew some quantum physics, complex analysis, and digital signal processing. The question is why you are forced to take a systems class instead of being allowed the depth that suits you.

    Am I impressed that someone came up with hierarchical directory structures, inodes, or virtual memory? Not really.

  6. the question is, why do grad students have to take any courses at all, instead of doing their research. seems to me the american system of postgraduate education is aimed at intimidating students and keeping them enslaved as long as possible.

  7. "I must admit that I find the fact that a computer science theory graduate student -- even one in complexity -- would ask such a question both sad and disturbing."

    It is kind of interesting in that, although I completely agree with your points, I actually have thought about this question quite seriously a fair amount recently. This was probably initially motivated, for me, by my having been a non-CS undergrad looking at the distribution requirements for theory graduate programs... and realizing that I know a lot more than the typical CS graduate about theory, but a lot less about systems or AI. (of course, I've run into at least one person with a MS in CS who did not know what complexity theory was, so this might not be saying much.)

    My point is that, particularly for a strongly theory biased person like me and, I'd assume, anonymous-graduate-student, it actually is worth asking the question. It's easy for mathematicians like us to lose sight of the answer. That said, with the exception of the issue of evaluating systems candidates, I've come up with almost exactly the same answers Lance stated. (the advice about not satisfying distribution requirements immediately, also; that seems to be a very common mistake around here.) It may just be that I'm too young and naive, but it seems to me that every way in which systems is *not* well grounded in theory is a potential avenue of research, with the potential to provide both interesting problems and useful applications.

  8. The question that Lance quotes is just a symptom that stem from the fundamental problem: that of regarding complexity theory as a subfield of computer science.

    Computational Complexity Theory is, scientifically speaking, a branch of *mathematics*. The current trends in the field, justify dropping all system courses requierments. Their place should be taken by algebra, analysis, advanced combinatorics and mathematical logic courses instead.

  9. Actually there are quite a few MATHEMATICIANS (affiliated to mathematics departments) - especially in Europe - that work on complexity theory.

    According to what Lance and others have claimed above, these guys are less competent researchers than CS guys. Since, this is not the case, I think that the points made above in support to system courses and their relevance to research are false.

  10. We can argue about the justice of it but most universities' math department salaries don't come close to their CS department salaries.

    If as a theoretician you aspire to a job in a math department then by all means replace your systems courses by math courses. If you want a job in a CS department then you'd better understand CS more broadly.

  11. There is also one more reason:

    - We want systems students to take theory courses

  12. 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.

  13. Hear hear! (re: Luca's comment)

    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.

    -ryan williams

  14. [...]that of regarding complexity theory as a subfield of computer science.

    Computational Complexity Theory is, scientifically speaking, a branch of *mathematics*.

    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).

  15. 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).

    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.

    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).

    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.

    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).

  16. "Just like theoretical physicists should do some experimental physics to realize what they do should have some grounding in reality"

    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.

    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.

  17. 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.

    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.

  18. Some very good theoretical work has arisen from questions from the systems community and vice versa.

    What would be good examples for the vice versa part, in fields other than Programming languages?

  19. A few examples, of theory work having impact in systems: streaming algorithms, Tornado codes and relatives, network coding.

    (and I am sure I forgot something)


  20. Piotr,
    can you expand on your comment? Is the impact of streaming algorithms etc. on systems concrete or potential, present or possibly future?

  21. 1. The analogy with experimental and theoretical Physics. CS is also about "something concrete", namely computations. Just as in Physics, computations exist independently of Theory. Their embodiments are programs running on computers. Complexity Theory is an abstraction, and a beautiful one, but one of the beefits of CS is that even a theoretician may "get one's hand dirty" and write code. You may choose never to do it, but if you never took serious Systems courses you are depriving yourself of part of the rich heritage of CS.

    2. As for a concrete influence of "Systems" on Complexity Theory look at the two papers

    M. Gentleman: Some Complexity Results for Matrix Multiplication in Distributed Processors JACM v25 n1 (1978)

    ABELSON, H.Towards a theory of local and global in computation. J. Theoret. Comptr. Sct. 6 (1978), 41--67.

    They addressed the problem of trying to quantify the amount of communication needed for some concrete problems on distributed computations. The concrete examples were numeric, but Abelson explicitly insisted that there was a fundamenta problem of computing here.

    At the next (11th, 1979) STOC, Andy Yao provided the right context for the question:

    Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213

    3. Finally, about eventually being in a CS Department, as a reason for taking Systems courses: I believe that as a matter of professionalism, any new PhD should be able to teach most undergraduate CS courses. This is certainly the case in Math, or Physics. I am not saying that this is the most productive use of his time, but there are many departments where this would be a big plus, if not an explicit requirement.

    My first job in the US was at Penn State. At the time it was very strong in Theory (my colleagues included Don Johnson, Greg Frederickson, Joseph JaJa, Jonathan Goldstine, Piotr Berman, Georg Schnitger, Steve Mahaney for a year, to mention only the people that I immediately remember). As a result, we were not very strong in Systems, and, in order to hire Theory faculty, we had to teach a reasonable number of Systems courses. I taught Compiler Construction, learned how to design VLSI circuits, had a student write his PhD dissertation on building a VLSI design tool based on a formalism like attribute grammars, yet I managed to be productive in Theory.

  22. 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.

  23. I haven't started my systems work yet, and I am dreading it...

    I guess I would posit the following analogy:

    theoretical cs - physics
    systems - engineering
    operating system - internal combustion engine

    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.

    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.

    -one of Lance's students

  24. I haven't started my systems work yet, and I am dreading it...

    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).

    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.

  25. 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.

    The one set of course requirements that might be useful to help students' careers: software engineering and computational finance!

  26. 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).

    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.

    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)

  27. 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?

  28. �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?�

    Yes. Your appreciation for beauty is dubious at best. I suggest you take an art course wherever you are. (Most universities offer them.)

  29. programming is a waste
    just use copy paste


  30. programming is a waste
    just use copy paste

    If no-one programmed, then what would you copy and paste from?

  31. Luca:

    We want systems students to take theory courses

    Clearly systems students should take theory courses, it's probably the only time these poor saps get to do something intellectually challenging!

  32. Clearly systems students should take theory courses, it's probably the only time these poor saps get to do something intellectually challenging!

    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".

    If you find symbol pushing "intellectually challenging", then unfortunately you belong to the class of "also-ran" theoreticians.

  33. --- Piotr,
    can you expand on your comment? Is the impact of streaming algorithms etc. on systems concrete or potential, present or possibly future?


    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.

    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.

    (additions/corrections welcome)


  34. 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.

  35. 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.

    If you don't want to take systems or AI courses you should seek a degree in some other discipline (e.g Math).

    I think it is as simple as that, regardless of whether they are pedagogical benefits or not(sometimes there are, sometimes there aren't).

    OTOH the European model is a bit different, it would be intersting to see what differences can be attributed to these different educational styles.

  36. 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.