Tuesday, April 11, 2006

What Math to Take?

A good reader question.
I was curious if you had any discussions on what kind of math background new graduate students need to have? For instance, if the undergraduate institution did not have a good math program to support the CS curriculum, what specific topics should students self-study before going to graduate school?
Most importantly you should have some familiarity with mathematical proofs. Mathematical maturity is more important than specific knowledge in any single topic.

Theoretical computer science is mostly discrete mathematics and other areas of discrete math play an important role: Discrete probability, combinatorics, algebra especially group theory, logic and number theory.

Depending on your interests analysis, measure theory, topology and algebraic geometry might be important. Almost every branch of mathematics has played some role in theoretical computer science.

I don't mean to scare you. As I said best to take any real math course (one with proofs, not just Plug-and-Chug Engineering math) and you can later pick up more specific math knowledge when you need it.

16 comments:

  1. shouldn't your response be don't worry about it, you won't be getting into grad school for comp sci anyway?

    ReplyDelete
  2. Lance: Good advice -- for once something I agree with! :)

    I've needed some approximation theory, some group theory, lots of linear algebra, and a little statistics and random walks. I did study some of these things as an undergrad, but I never really learned them until I needed them.

    ReplyDelete
  3. What funny is that in the past I've seen mathematical types complain about "having to program" and programmer types complain about "having to write a proof." For me, I'd get chills proving that 0*a = 0 (in group theory) or showing that something was undecidable.

    To me these activities are far too similar. At least at the junior and senior undergraduate level. There's even a degree of type systems in there: if you need to prove some scalar satisfies P(x), you better not end up with a set or a vector.

    In both cases, you also need to get over the tactical problems. For any 100 line program or single page proof, there are probably a dozen stupid little "tricks" that you just need to learn from reading other proofs/programs or through experience. Getting hung up on the syntactic/semantic rules and the early tactical tricks just clouds the strategic activity, where designing an algorithm is similar to designing a proof.

    And if you don't believe me, take it up with Curry and Howard.

    ReplyDelete
  4. Great advice.

    Another way of restating it: you should have enough Math to be able to learn new topics pretty much on your own--if you do any Theory, you'll need it.

    A serious course in Linear Algebra is a good place to start. It should be rigorous and general. Linear Algebra has real theorems, but most are not excessively long or hard. It has applications all over the place in CS, from Quantum Computing to Google tricks, in combinatorics, information retrieval, learning, coding, and numerical computation.

    There is no telling what Math will be useful in your research. To give an idea of the diversity of useful mathematical tools, in the last few years I've seen my colleagues use
    not only the more or less "standard" background of Computability Theory, Graph Theory, Linear Algebra, and Combinatorics, but also Fourier Analysis on groups, martingales from Statistics, Measure Theory, Theory of Games, Nonlinear Programming, Measure Theory, Algebraic Geometry, Fixpoint Theorems from Topology, Coding Theory, Laplace operators from Analysis, calculus on manifolds, Markov Chains, and Approximation Theory. All of these are from research at Chicago, and I omitted everything from the PL/Semantics side, like Type Theory, Lambda Calculus, Proof Theory and the like.

    You can't learn all of this before grad school, or even in it. You have to learn enough not to be intimidates, and be able to learn quickly.

    ReplyDelete
  5. Algebra algebra algebra. And some more algebra. Its not just useful, its also pretty.

    ReplyDelete
  6. (The lists people have been describing mostly relate to CS theory but for graphics and vision, in addition to linear algebra, topics like differential geometry are also valuable/essential.)

    I was an undergraduate math major and can't think of a math course that I took that hasn't been useful in understanding some CS theory paper or other. On the other hand, self-study is also important. For example, Lance mentioned discrete probability as an important area. The most useful aspect in lots of CS theory work has been the "probabilistic method" but you would be hard-pressed to find an undergraduate course on the subject. It is extremely accessible, perfect for self-study, and there are some great texts like Alon and Spencer's
    text on the subject.

    ReplyDelete
  7. I think if you intend on applying for graduate schools in theoretical computer science, you're shooting yourself in the foot by not having any mathematical coursework in your background. I get the impression that it's something that admissions committees look favorably upon (at least for theory).

    ReplyDelete
  8. If I could go back now and change the math courses which I took when I was an undergraduate, I would get rid of algebraic geometry (which I was not mature enough to appreciate) and of differential geometry, and I would add probability, statistics, and advanced linear algebra. Mostly I agree with Scott.

    ReplyDelete
  9. On the other hand, by far the best math class I took as an undergrad was topology. I've never needed it once in my research, but it was way more fun than linear algebra or analysis.

    ReplyDelete
  10. As people suggest, the most important math skill to get as an undergrad is math agility--the ability to feel comfortable picking up and learning new topics. In the best case, CS theory hopefulls would do a double major.

    On the other hand, I don't think it's that important (at the undergrad stage) to pick up specifically useful mathematics. The reason is that until you have some experience (at least 4-5 high level math courses), it's very difficult to approach new math from the right stand point--you don't yet have a philosophy, or a way of partitioning the world so the new concepts and problems look like the old ones, just in different clothing.

    So, as Scott seems to advocate, you should just take things that seem "cool" to you. Topology, complex analysis, galois theory, number theory, etc. The unfortunate thing about differential geometry is that, while it's a beautiful subject, it is often taught at an incessantly boring level of generality, so you need a lot of stamina just to get to anything interesting.

    ReplyDelete
  11. Whatever you learn, it won't be enough.

    You'll have to learn new things and (more importantly) appreciate them at a deeper level to succesfully do research.

    Scott mentioned this in his long-ago guest-blogging gig, you can only REALLY appreciate something when you actually use it in your OWN work.

    In fact, I might even advice this undergrad to forget about taking courses and just try to find a good theory problem and work hard on it.

    You will probably learn plenty of math along the way and a STOC/FOCS paper is probably more impressive than any number of graduate math courses!

    But yeah, if you're going to take math courses, just mastering the notion of proof is more key than the specific content, so any number of courses could serve the goal pretty well.

    ReplyDelete
  12. A couple of anonymouses above have suggested that you won't get into CS grad school unless you have a lot of math courses.

    My observation leads me to think that this is NOT a huge factor in the admissions decision.

    They want to know if you'll be a good RESEARCHER not if you are a good course taker or if you are "someone who knows a lot of math."

    To this end the biggest factors are:
    (1) Recommendations from other succesful researchers (e.g. your professors).

    (2) The research that you've actually participated in.

    Of course, having a lot of math courses on your transcript certainly won't hurt you, but its probably not going to influence the admissions decision that much(compared to the other factors involved).

    ReplyDelete
  13. Theoreticians need a sound mathematical education, and that's acquired usually through analysis and algebra. Some probability theory and discrete mathematics won't hurt. Other than that, my advice is to take math courses that you like. You'll do a better job absorbing the course material if you are motivated by interest rather than perceived usefulness.

    ReplyDelete
  14. I have the following situation, related to this discussion. I have a PhD student early in his Phd career that thinks that he wants to do theory. But
    his mathemtical background/skills are too weak at this point to be able to obtain results publishable in the theory literature. I am try to decide whether it would be better to advise him:
    * Take 1-2 years of mathematics courses to build up his skills, and not worry too much about publishing, or
    * Try to build his skills by trying to get publishable results, even though initially there is little chance for success

    The students hinks he really wants to do theory.

    ReplyDelete
  15. Grad school is so cushy--there's time to sleep in, party, do research, and learn. If you feel like it, you can take a week or a month off and no one notices.

    So why shouldn't you be expected to work hard? Why can't he both take math courses, and do research?

    ReplyDelete
  16. Generic advice I give to students who've asked me that question is:
    The math you learn is the math you'll use, and the math you use is the math you'll learn. I think that the more mathematical expertise the community has, the more chances we have of finding the right area of mathematics to solve any particular problem. Each researcher gets an ``edge'' in solving the problems susceptible to the branches of mathematics and techniques that that researcher knows BETTER than the other researchers. So we shouldn't all study the same math.

    On the other hand, as other people have also pointed out, I don't really feel that I've understood a mathematical topic until I can apply it to solve some problem that I didn't know previously. Often, I don't ``apply'' a technique I previously learned as much as solve a problem and then RECOGNIZE the technique I used as being one I read about previously. Then I understand the technique.

    Russell Impagliazzo

    ReplyDelete