tag:blogger.com,1999:blog-3722233.post114475526396822716..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: What Math to Take?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-88966672729823192732016-11-23T02:20:40.570-05:002016-11-23T02:20:40.570-05:00I studies CS for the Bachelor degree. I regret my ...I studies CS for the Bachelor degree. I regret my decision now. If I had the choice again, I would study MATH and PHYSICS, then you can do a masters in CS easily. From my view, it is a crime to a have Bachelor program in CS. Because you will later find yourself having much difficulty in advanced topics. You need tons of math from every direction in Masters of CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144881427015934632006-04-12T18:37:00.000-04:002006-04-12T18:37:00.000-04:00Generic advice I give to students who've asked me ...Generic advice I give to students who've asked me that question is:<BR/>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. <BR/><BR/>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. <BR/><BR/>Russell ImpagliazzoAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144868265395618652006-04-12T14:57:00.000-04:002006-04-12T14:57:00.000-04:00Grad school is so cushy--there's time to sleep in,...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.<BR/><BR/>So why shouldn't you be expected to work hard? Why can't he both take math courses, and do research?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144856765809731512006-04-12T11:46:00.000-04:002006-04-12T11:46:00.000-04:00I have the following situation, related to this di...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 <BR/>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:<BR/>* Take 1-2 years of mathematics courses to build up his skills, and not worry too much about publishing, or<BR/>* Try to build his skills by trying to get publishable results, even though initially there is little chance for success<BR/><BR/>The students hinks he really wants to do theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144834836109080762006-04-12T05:40:00.000-04:002006-04-12T05:40:00.000-04:00Theoreticians need a sound mathematical education,...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144819423239196152006-04-12T01:23:00.000-04:002006-04-12T01:23:00.000-04:00A couple of anonymouses above have suggested that ...A couple of anonymouses above have suggested that you won't get into CS grad school unless you have a lot of math courses.<BR/><BR/>My observation leads me to think that this is NOT a huge factor in the admissions decision.<BR/><BR/>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."<BR/><BR/>To this end the biggest factors are:<BR/>(1) Recommendations from other succesful researchers (e.g. your professors).<BR/><BR/>(2) The research that you've actually participated in.<BR/><BR/>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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144818166998061522006-04-12T01:02:00.000-04:002006-04-12T01:02:00.000-04:00Whatever you learn, it won't be enough. You'll hav...Whatever you learn, it won't be enough. <BR/><BR/>You'll have to learn new things and (more importantly) appreciate them at a deeper level to succesfully do research.<BR/><BR/>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.<BR/><BR/>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. <BR/><BR/>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!<BR/><BR/>But yeah, if you're going to take math courses, just mastering the notion of <I>proof</I> is more key than the specific content, so any number of courses could serve the goal pretty well.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144817398563447462006-04-12T00:49:00.000-04:002006-04-12T00:49:00.000-04:00As people suggest, the most important math skill t...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.<BR/><BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144805313935710642006-04-11T21:28:00.000-04:002006-04-11T21:28:00.000-04:00On the other hand, by far the best math class I to...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 <I>way</I> more fun than linear algebra or analysis.Scotthttps://www.blogger.com/profile/12161309448306097395noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144802126511550082006-04-11T20:35:00.000-04:002006-04-11T20:35:00.000-04:00If I could go back now and change the math courses...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144775584556928272006-04-11T13:13:00.000-04:002006-04-11T13:13:00.000-04:00I think if you intend on applying for graduate sch...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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144774725472043182006-04-11T12:58:00.000-04:002006-04-11T12:58:00.000-04:00(The lists people have been describing mostly rela...(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.)<BR/><BR/>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<BR/>text on the subject.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144774098784952582006-04-11T12:48:00.000-04:002006-04-11T12:48:00.000-04:00Algebra algebra algebra. And some more algebra. It...Algebra algebra algebra. And some more algebra. Its not just useful, its also pretty.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144768464943154492006-04-11T11:14:00.000-04:002006-04-11T11:14:00.000-04:00Great advice. Another way of restating it: you sho...Great advice. <BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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<BR/>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.<BR/><BR/>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.Janos Simonhttps://www.blogger.com/profile/15677985672817404601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144765004719182782006-04-11T10:16:00.000-04:002006-04-11T10:16:00.000-04:00What funny is that in the past I've seen mathemati...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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>And if you don't believe me, take it up with Curry and Howard.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144759517121902692006-04-11T08:45:00.000-04:002006-04-11T08:45:00.000-04:00Lance: Good advice -- for once something I agree w...Lance: Good advice -- for once something I agree with! :)<BR/><BR/>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 <I>really</I> learned them until I needed them.Scotthttps://www.blogger.com/profile/12161309448306097395noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1144757440819570452006-04-11T08:10:00.000-04:002006-04-11T08:10:00.000-04:00shouldn't your response be don't worry about it, y...shouldn't your response be don't worry about it, you won't be getting into grad school for comp sci anyway?Anonymousnoreply@blogger.com