35
$\begingroup$

I'm a freshmen studying computer science and I already know that I want to go into academia with focus of theoretical comp sci. I already read some of papers referenced in this question and this question convinced me further.

What should I be doing now, as an undergrad, to get involved in the field? What can I do to prepare for research in the field?

$\endgroup$
  • 7
    $\begingroup$ This isn't really significant enough to post as an answer, but consider picking up a copy of Michael Sipser's "Introduction to the Theory of Computation," too. Even if you don't have time for self-study with that book, it's a great reference if there's anything you need to look up that isn't clearly explained on Wikipedia. $\endgroup$ – Philip White Dec 20 '10 at 3:23
  • 2
    $\begingroup$ I don't know how the procedure works, but I'd love to see this as community wiki. $\endgroup$ – chazisop Dec 20 '10 at 4:17
  • 3
    $\begingroup$ flag the question for moderator attention and we'll deal with it. $\endgroup$ – Suresh Venkat Dec 20 '10 at 13:37
  • 2
    $\begingroup$ @Good Person: OP can not make a question CW, only moderators can. $\endgroup$ – Kaveh Dec 21 '10 at 5:29
  • 2
    $\begingroup$ @Good Person: as Kaveh mentions, original posters can't make posts CW anymore (and neither can anyone with edit privileges). Only mods can do this. no offense was intended. $\endgroup$ – Suresh Venkat Dec 21 '10 at 6:04
29
$\begingroup$

Let me provide an answer from the other side. I've had a few undergraduate student researchers work with me. The experience has been mixed: with some, I have published papers and have work in progress, and with others, we never really got off to any kind of start.

It's great that you know what you want to do. As an undergraduate, here's what you should be focusing on:

  • Building the mathematical "muscles" that will help you when you start working on problems in earnest
  • Exploring different aspects of theoretical CS to get a sense of the area and figure out what kinds of problems/areas you find interesting
  • (depending on the area) working out some puzzles, maybe solving some exercises, and working your way up to a research question.

Find a professor to guide you, and PUT IN THE TIME ! The hardest thing you'll face is creating the open time to think about problems in the midst of classwork, assignments and exams. But you need to reserve blocks of time for your independent study and research otherwise it will be very hard to make any kind of progress. How you do this is upto you: maybe you can find a professor to meet with you once a week and set intermediate goals for you, or maybe you can set a long term goal (working through X exercises from a text) and work steadily on that.

$\endgroup$
  • 4
    $\begingroup$ Nice answer! "you need to reserve blocks of time for your independent study": this remembers me of my own experience. I used to be a lazy math student, then in master I discovered a nice TCS problem (centered around the busy beaver function). I started working on my free time on it with guidance by one of my prof. I never found something interesting on the problem, but 12 years later, I wrote more than 15 papers with him (but he never was my phd/master advisor, only an "external" mentor). $\endgroup$ – Sylvain Peyronnet Dec 20 '10 at 18:06
  • 1
    $\begingroup$ Suresh's answer is great! To the OP: Building mathematical "muscles" means getting used to the language and tools of math (combinatorics, graph theory, analysis etc) and also getting used to prove theorems! (And this is the really exciting part! :-) $\endgroup$ – Jay Dec 25 '10 at 9:12
19
$\begingroup$

I'm currently a PhD student and not a prof, so my suggestion comes from my (limited) personal experience as a graduate student.

When I was an undergraduate student, I always worked as a research assistant in summer with different profs in my department. I personal believe that the only way to figure out if TCS is truly for you or not is to work on concrete problems and see what you can enjoy the most. It did take me quite a while to find a prof and a topic that I liked. There's also a "social" aspect in research, and different profs have different working and supervision habits, and thus these summer research jobs will give you a better idea what quality you want the most from a supervisor in the future.

There are many interesting fields in Computer Science, and TCS is just one of them. So it's always best to keep your options open and talk to different profs. It's very important to specialize when you're doing PhD, but as as an undergrad I think Mark Braverman's advice is extremely relevant:

" Try to learn as much as you can. [...] It is more difficult later on!"

[Mark tried to enroll in many courses (well above the limit), and explore different areas of Mathematics and Computer Science when he was an undergrad.] Try to attend lectures and seminars on different topics in your department. When you're in your upper years, you should also ask for permission to audit graduate courses related to your interest.

Also depending if you're majoring in Maths or CS, you also have to plan courses you should take to prepare you a solid basic foundation. If you're a Maths undergrad, then you should take more CS courses in algorithms and complexity which give you a more "algorithmic" mind. If you're a CS or Engineering undergrad, then it's always a good idea to learn some basic Maths courses in:

  • Combinatorics
  • Probability and Statistics
  • Advanced Linear Algebra
  • Abstract Algebra
  • Analysis

It's true that you can never learn enough Maths, and that you should learn to pick up new Maths/methods/techniques fast whenever needed. But a solid background will definitely give you an easier start into TCS.

I wish you the best of luck and success!

$\endgroup$
  • 6
    $\begingroup$ +1: nice answer. I will add that taking/auditing non-theoretical CS or non-CS courses is also a good thing, it open ups your mind for possible problems to work on, you never know where a nice theory question shows up, so keep your eyes open. :) $\endgroup$ – Kaveh Dec 20 '10 at 6:33
  • $\begingroup$ Would you recommend "Advanced Linear Algebra" by Steve Roman for graduate self-study? $\endgroup$ – Jacob Mar 6 '11 at 7:20
  • 2
    $\begingroup$ @Jacob: Roman's book is certainly recommended by many people. It is really advanced and covers nice topics like modules, convexity, affine geometry, tensor products, etc. But the bottom line is you should always choose something that is suitable for your taste and background! So scanning through a bunch of books in the library before deciding is always a good idea (at least for me). $\endgroup$ – Dai Le Mar 6 '11 at 10:21
11
$\begingroup$

As a freshman undergraduate, your best bet is to express this interest to your professors in the CS department, who can help you out (providing this help a big part of their job!). Most of them would, I would expect, be delighted to help out an undergraduate who was interested in the same things they are. At the very least, they can give you good advice about what classes to take at your institution, and advice that is customized to your situation.

$\endgroup$
10
$\begingroup$

Lots of other folks seem to be giving various pieces of good advice. To add to the wisdom, let me say this: There is no such thing as knowing too much math (unless you decide you want to do pure math instead). Seriously, know your analysis, combinatorics, algebra, maybe some rep theory, alg top, and so forth. It makes being widely read across areas of CS theory much much much easier :)

$\endgroup$
  • 2
    $\begingroup$ excellent advice. I tell this to all undergrads who come talk to me as well. $\endgroup$ – Suresh Venkat Dec 23 '10 at 6:14
7
$\begingroup$

You've made a great first step! I'll second pboothe about talking with a professor in your department. If you are interested in theory, find whoever is teaching the theory courses and talk with them. They may have some problems that don't require too much background to get started on. In my personal experience, there are more problems in graph theory and combinatorics that are more approachable than theory, but still build the same research skills. Don't be afraid of your math department!

It may also help to start getting involved in the community, especially by asking and answering questions here. It would help to have your username be your own name so we know who you are.

$\endgroup$
6
$\begingroup$

I'm an almost graduate student. So the answers to your question are also interesting for me, but perhaps my little personal experience can help.

Here is my list (in random order) of suggestions what you can do:

  • First of all read as many papers/books/lecture notes as you can find. But it is also important to apply your knowledge to exercises and later to open problems! Some of my tutor always says: Not only your muscles need continous training :)
  • Read/Ask/Answer questions on this site (or some other related SE site) is a good way to learn how to work with research topics in TCS or math.
  • I try to read a lot of TCS blogs from well-known researcher. The topics cover both current and historical results.
$\endgroup$
  • $\begingroup$ Would you have any links to those blogs? $\endgroup$ – SH7890 Mar 30 '18 at 3:02
2
$\begingroup$

I think the most important thing is to explore as widely as possible to learn what aspects of TCS really excite you. In the course of this exploration you might find that the problems that intrigue you the most are the intersections of TCS with other fields (e.g.economics) or applications of TCS (e.g. to computer networks) or TCS topics which are also part of other areas in CS like computational or statistical learning theory. Heck, it is even possible you might change your major to math or physics or something related if your interests take you in that direction.

My point is that as a freshman you really have an opportunity to explore widely with less pressure than you would as a grad student or professor. And to not be alarmed if you don't end up in the "usual suspect" TCS topics.

Of course it would be ideal if you go "deep" in some area, learn solid techniques and publish great results.

And if you end up becoming an expert in a hot new field before it becomes mainstream that will probably be great for your career.

$\endgroup$

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.