10
$\begingroup$

I'm looking for a major in Theoretical Computer Science; specifically, I'm interested on complexity theory and probabilistic automata theory. As I'm graduating in one year, what advanced courses in math (like Galois theory or Harmonic analysis, for example) do you think would be useful to take over the next two semesters? Why?

$\endgroup$
  • 2
    $\begingroup$ See related question. $\endgroup$ – Nicholas Mancuso Sep 7 '12 at 5:05
  • 1
    $\begingroup$ Also check course requirements at your school, as well as similar questions on Theoretical Computer Science (e.g. this or this). I am tempted to close this one here as a duplicate; it's also pretty localised. $\endgroup$ – Raphael Sep 7 '12 at 7:40
  • 5
    $\begingroup$ Take ALL the math! $\endgroup$ – JeffE Sep 7 '12 at 12:21
  • 2
    $\begingroup$ @JeffE Take... all the math? $\endgroup$ – MrGomez Sep 7 '12 at 18:14
  • 2
    $\begingroup$ All the math in A Theorist's Toolkit. $\endgroup$ – Chao Xu Sep 8 '12 at 0:16
2
$\begingroup$

(A summary of the comments to the questions)

pretty much any area of mathematics could be important in TCS, so you should do the best to strengthen your math background. Any tool you learn is a gain, and may be employed in some TCS (sub-)field.


This question was also answered in other SE, and very informative details can be found in:

  1. what-kind-of-mathematical-background-is-needed-for-complexity-theory
  2. Examples of “Unrelated” Mathematics Playing a Fundamental Role in TCS?
  3. What math courses should I take to prepare for a CS masters or PhD?
$\endgroup$
  • 1
    $\begingroup$ Strongly disagree with this blanket statement. In fact, the vast majority of areas in mathematics are not helpful for theoretical computer science. Say functional analysis, set theory (e.g. forcing), topology, algebraic geometry (no, GCT doesn't count), differential equations, and the list could go on and on. The most important mathematical subject is probability theory (even that depends on the kind of TCS you're doing). Apart from that, some very basic knowledge in some areas, e.g. group theory. $\endgroup$ – Yuval Filmus Oct 5 '12 at 3:45
  • $\begingroup$ @Yuval, I think that this is a bit of short-sight. Who thought Fourier Transforms can be so useful to TCS (before the glory it achieved when used for PCP, etc?) Who thought SDP solvers are so relevant to TSP (as recently showed in [arxiv:1111.0837], if I understand their work correctly).. I Think many other methods can be used for TCS and surely for CS in general.. True, not all of the methods are equally important, and I was hoping this thread would become a list of methods/applications, where the most important methods would get the highest votes. $\endgroup$ – Ran G. Oct 5 '12 at 13:14
  • $\begingroup$ Fourier transforms are very elementary concepts. You don't need to understand the Fejer kernel in TCS. As for SDPs, they come from operations research (or convex optimization, if you prefer). It's true that some things might be useful. For example, I found my background in C very useful, and Virginia Williams found her background in Maple very useful. In terms of your career, writing and public speaking are also very useful. All of these are probably more useful than a course on combinatorial set theory. Why not tell people to study these subjects instead of random math courses? $\endgroup$ – Yuval Filmus Oct 5 '12 at 20:17
  • 1
    $\begingroup$ @YuvalFilmus I don't understand: the MMO invariance principle is a strict generalization of Berry-Esseen. I don't agree with your larger point either. A lot of TCS may use probability as far as a Chernoff bound. But the JL-lemma, concentration of measure in say ARV, Dvoretzky's theorem for compressed sensing, Grothendieck's inequality in approximating the cut norm are just some very successful examples of FA being useful in TCS. yes, the mainstream focus of the two fields is different - but the intersections go beyond "the first 10 pages" and make learning the math worth it. $\endgroup$ – Sasho Nikolov Oct 7 '12 at 7:31
  • 1
    $\begingroup$ moreover, while our applications usually allows us to stick to (variants of) results that can be described and often proved in an elementary way, the larger context provides intuition (CLT is a great heuristic for example). and since it's hard to tell what's useful until you need to use it, i wouldn't mind taking some math courses in addition to reading groups in TCS that help you learn what's already known to be useful. i've recently found a FA result (that's almost never used in TCS afaik) to be the key to a problem I was working on $\endgroup$ – Sasho Nikolov Oct 7 '12 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.