Welcome to TCS @ Illinois!

First, read:

• the bulleted advice at the bottom of this page and
• the Recommended Program of Study, which offers advice on what courses you should take while you are here, since in some sense, there are no required courses.

Once you’ve read those, you probably know about the theory seminar and the theory reading group, and if you haven’t signed up for the mailing lists, do it now! Here are the links again: theorycs, theory-seminar, theory-reading-group. Up-to-date links to the current seminar and reading group schedules can always be found at the landing page for this site.

As noted in the Recommended Program of Study, courses of interest to students in theoretical computer science can be found in several departments at this university, including Math, ECE, and ISE. We keep an incomplete list of these courses at the Current Courses page of this site. Please suggest a course if you think it’s missing*!

*Ask the current graduate students who is currently maintaining the list. Someone will know.

Now, you’re probably wondering about the qualifying exam. After you read the Qualifying Exam page, chat with other students, especially third-years and up, about qual prep.

• In your first week, find some of the senior grad students, and talk to them about this list!
• Take Graduate Algorithms (CS 473) in your first semester, and Complexity Theory (CS 579) in your second semester. You may know much of the material in 473, but there will likely be some things that you do not know, and if you find the course easy, that gives you more time to work on other things.
• Take one non-theory (breadth) course some time in your first year, preferably in your first semester, so you can get this requirement out of the way. There are lots of great courses offered outside theory; take something that you might be interested in.
• Do not take Combinatorics (Math 580) in your first semester without good reason; fall of your second year is a good time. Make sure to take it before taking the qual, though.
• Join the theory and theory-seminar mailing lists, and attend theory seminar regularly. Do not register for any other course that might conflict with the theory seminar, and make sure you give a talk there. Talk to a professor to get a paper if you don’t have anything that you want to present. Talk to the senior students for more paper/talk ideas.
• Join the theory-reading-group mailing list and attend theory reading group regularly. Make sure to present at one of the reading group sessions, especially if the scheduled topic is something you are not familiar with. Teaching is one of the best ways to make yourself learn something.
• Go to lunch with the theory faculty and other theory students. This is as easy as popping by their office(s) and asking, “lunch?”. If eating with the faculty members intimidates you, that’s more reason to go! The faculty were all grad students in the not-too-distant past, and they remember what it’s like. It’s a great way to get to know the rest of the group better; you can find out what people are working on, get advice about life in and out of school, and much more. A lot of great ideas grow out of random conversations.
• Do an independent study with one of the theory professors in your first semester. Use the semester to learn about their research area(s), read some interesting papers, and find out if this is an area you might be interested in working on, or an advisor you might be interested in working with. If your work leads to a paper, great, but the lack of one shouldn’t worry you at all. Feel free to do an independent study with a different professor the next semester, or with two professors in a single semester; they won’t mind at all.
• While doing an independent study, set a time for a weekly meeting with the professor. Note that this does not mean that you can’t meet them at other times; they almost always have a few minutes to answer questions, or just chat. If you’re just beginning to work with someone, and you’re not sure what you’re interested in, download several of his papers, and read the abstracts and introductions. Pick 3-5 papers that seem interesting, and read them carefully. If you have any questions, go to the professor and ask him to explain the parts you didn’t understand. Also, talk to his current grad students, and ask them what they’re working on; the grad students are also glad to answer questions about papers, about working with the professor, or about anything else.
• Alternatively, special topics classes (CS 498 and 598) are a good way to work with a professor if you can’t get an independent study, or think you might be interested in more than one area.
• Start keeping a research notebook. Write down all the problems you come across, especially if you think they are interesting (or if you solve them). You’ll find yourself referring to this for ideas in later years.
• A slightly more controversial recommendation, not unanimously agreed upon: In your first year, don’t work on a research problem if you can’t explain the problem in 5 sentences or less to a typical incoming theory grad student. There are several exceptions to this rule (for instance, if you’ve been working on the problem domain already). Lots of excellent work can be done in highly specialized or technical areas, but you’ll have plenty of time to work on them later, and these are often not the best introductions to a research area.
• A closely related point: While considering special-topics theory courses for your first year, a similar rule applies. Take classes in Computational Geometry, Randomized Algorithms, Data Structures, or Approximation Algorithms. These have broad themes, and some of the techniques are likely to be useful in whichever research area you go into (and on the qual!). Classes on expander graphs, metric embeddings, and other specialized topics should be much lower on the list, although they are not a bad idea if they are with a professor you think you want to work with.
• Don’t start working on old qualifying exam problems until the end of your first year. Your first few problems will probably seem difficult, so start working on problems the semester before your qual so that you can pinpoint your weak areas in time to work on them. If at all possible, try to study with others in your year who are taking it; if not, ask the older students for help with some of the harder problems you get stuck on. Make sure you meet with all the theory faculty members at least a few times to talk about your qual; discuss what they expect you to know and do. They are always happy to help you with difficult problems, and to suggest books or other reference material. The wiki has a qual page with more information.
• Above all, try to find an advisor you can work with by the end of your first year. You must have an advisor in order to sign up for the qual, and it’s a good idea to work together for a little while to be sure you are compatible.
• When searching for a problem, everyone will tell you to find something you want to work on. While this is important, it is also important to find a problem that your advisor also wants to work on. (The best way to do this is to find an advisor who wants to work on the same things you do!) It is possible to finish a thesis while working on something that your advisor is not that interested in, but it is much harder, and generally requires finding an outside person (e.g. someone you meet at an internship) to work with instead. If at all possible, look at problems closely related to your advisor’s area, and make sure he is also excited about the problem.
• Try to attend conferences as much as possible. In your first year, this probably will just be Midwest Theory Day and other local opportunities. However, after you have passed the qual, make sure to ask your advisor if you can attend a larger conference or workshop. He should be able to suggest a useful one for your research area.
• Meet all of the theory faculty. This should be possible by attending theory seminar and/or the theory lunch, but it’s also a good idea to take a class with as many as possible. They should all know you on sight within your first month here.
• Likewise, meet the other theory students. We are all in the same general area near the faculty, so stop by. Set aside at least half an hour a week to talk to the older students; ask us about research, classes or anything else, or just rant about grad school. Older students can be a good source of advice and neat research problems.
• Go to lunch with the theory faculty and other theory students. This is as easy as popping by their office(s) and asking, “lunch?”. If eating with the faculty members intimidates you, that’s more reason to go! The faculty were all grad students in the not-too-distant past, and they remember what it’s like. It’s a great way to get to know the rest of the group better; you can find out what people are working on, get advice about life in and out of school, and much more. A lot of great ideas grow out of random conversations.
• Do an independent study with one of the theory professors in your first semester. Use the semester to learn about their research area(s), read some interesting papers, and find out if this is an area you might be interested in working on, or an advisor you might be interested in working with. If your work leads to a paper, great, but the lack of one shouldn’t worry you at all. Feel free to do an independent study with a different professor the next semester, or with two professors in a single semester; they won’t mind at all.