What kind of mathematical background is needed for complexity theory?

I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are considered helpful for TCS, especially (classical) complexity theory.

What fields do you consider essential for someone that wants to study complexity theory? Do you know of any good textbooks covering these fields and if yes, please include their difficulty level (introductory,graduate etc.).

If you consider a field that is not heavily used in complexity theory but you consider it critical for TCS, please also refer it.

• I'd recommend that you start reading a standard text on complexity theory, like Arora/Barak or Papadimitriou, and whenever you get stuck because you don't understand the math, try learning the associated math in some detail before proceeding. – Robin Kothari Oct 31 '10 at 6:08
• After you have done what Robin suggested, start to work on some small open problems. You will feel stimulated to learn the math that is behind it. As a grad student, I don't find very efficient to learn some mathematical field just for the sake of learning. – Alessandro Cosentino Oct 31 '10 at 16:18

If you look at the answers to this TCS StackExchange question, you'll see that there's a possibility that pretty much any area of mathematics could be important in complexity theory. So, if you're really interested in some area of mathematics that doesn't seem to be related, go ahead and study it anyway. If it ever does become relevant to complexity theory, you'll be one of the few complexity theorists who understands it.

• This answer doesn't mean you shouldn't study the fields we know are related (see the other answers). I would say these include linear algebra, graph theory, probability theory, basic abstract algebra, and basic logic. – Peter Shor Oct 31 '10 at 17:59
• Of course, if you want to do something like contribute to Mulmuley's program for proving P$\neq$NP, you need much, much, much more mathematics than this. – Peter Shor Nov 21 '10 at 14:23

You should add Dexter Kozen's book on the theory of computation to your list. Covers the basics of complexity theory very effectively, and the short lecture format is great.

In terms of mathematical background, in addition to what's mentioned above:

• Probability theory
• Linear algebra and abstract algebra
• graph theory
• basic logic

I don't think you need to be a master of these topics to start, but it definitely helps to have a certain comfort level.

$\bullet$ The book Extremal Combinatorics, by Stasys Jukna, is IMO too little-known within the complexity community. It's a great collection of combinatorial techniques written largely with an eye to their applications in TCS (mostly complexity). A number of important complexity techniques are discussed in their combinatorics context, including famous results like monotone- and $AC^0$-circuit lower bounds, but also some very nice results you might not otherwise encounter. And there's lots of exercises.

It is (to my knowledge) the only published book that treats the 'linear algebra method in combinatorics' in depth--a slick, powerful tool to know about. There's a draft manuscript of Babai and Frankl that goes into much more depth, but that's not published or online:

https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science

$\bullet$ As you probably know, the probabilistic method in combinatorics is very important, even central, in complexity theory. Jukna's book covers it, but it is treated in greater depth (with many other beautiful examples) by Alon and Spencer's famous book The Probabilistic Method.

• Along the same lines, I want to point out the beautifully written guide to the entropy method, "Entropy and Counting," by Jaikumar Radhakrishnan. The entropy method is another of those slick tools that are very satisfying to apply when the right opportunity comes by. – arnab Oct 31 '10 at 21:28

The previous answers already listed the basic ones: probability theory, combinatorics, linear algebra, abstract algebra (finite fields, group theory, etc).

Fourier analysis, see, e.g., Ryan O'Donnel's course: http://www.cs.cmu.edu/~odonnell/boolean-analysis/

Information theory, the standard book is Elements of Information Theory: http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954

There's also representation theory, random walks, and many more I probably forget...

• Most of the stuff you just learn as you go, depending on where research/life takes you: from courses, from lectures, from collaborators, from papers, etc. – Dana Moshkovitz Nov 1 '10 at 0:45

Apart from basic stuff, probably:

• Combinatorics -- You might find youself counting things quite regularly
• Stochastics -- For average case analyses and randomized algorithms

I like Concrete Mathematics by Knuth. It gives a good overview/basic knowledge of many important tools.

If you like generating functions (see generationfunctionology by Wilf) as a tool, complex analysis comes in handy, too.

• I love Concrete Math, but it is a bit esoteric. I would recommend a more mainstream book first, like Cameron's "Combinatorics". – Emil Oct 31 '10 at 18:11
• Here's my impression--Concrete Math seems to be an awesome book to learn how to do exact (or nearly exact) analysis of algorithms, Knuth's forte. If that's what you want to do, rock on. But be aware that most complexity theory papers give much less precise bounds, so the techniques of CM are less relevant. – Andy Drucker Oct 31 '10 at 23:36
• Some might say this is because complexity theorists are lazy bums. But I think it's because (a) exact bounds can be more effort than it's worth, (b) often there's such a large gap between known upper and lower bounds that small refinements on either side can seem of little value. – Andy Drucker Oct 31 '10 at 23:39
• I should say, there's all kinds of cool stuff in the book--my remarks mainly concern the material on exact solutions of summations and recurrence relations. – Andy Drucker Oct 31 '10 at 23:44

Sanjeev Arora has a nice document for a grad course (for 1st year students) he taught called the "theorist's toolkit," which has a lot of the basic material a theory student should know. A lot of this stuff you can wait until grad school to learn, but it will give you a good idea of what you'll need to know and some of the prerequisites.

A common, though certainly not universal, paradigm for many successful researchers in the TCS community is as follows: Know a few basics at an undergraduate level, such as logic, linear algebra, probability, optimization,graph theory, combinatorics, basic abstract algebra. Beyond that, don't force yourself to learn anything else until you really think you need it to crack that problem you've been struggling with for months, or if you think you would really enjoy learning something for the sake of it.

"How do I know that I need it if I've never seen it before?", you ask? Good question. Sometimes you get lucky and sense it: "You know what, this sub-problem I'm trying to tackle sounds a lot like that fourier transform thingamajiggy Fred won't shut up about. I'll have to check that out or trap Fred in a room and have him give me a quick run through the basics." Other times, you trap a bunch of more knowledgable people than yourself in a room, say by giving a seminar talk or something, and whine about how you can't solve this problem until Fred chimes in with "Hey, I bet you that you can solve this with Fourier Analysis. Let me show you how." In the end, you get a joint paper with Fred, you learned something new, and you and Fred are best buddies now and go out drinking every other Saturday night. Not a bad system.

I think a list of fields of mathematics that are not useful would be much shorter than a list of fields that are! I can't think of any.

Study whatever math looks interesting, and/or whatever it looks like you need at the moment. Even if you don't use it directly, it'll help you learn other stuff that you do.

• I'll second this answer. Whatever math you find most interesting will guide you to what problems are most interesting as well as problems that you are well-suited to solve. – Derrick Stolee Oct 31 '10 at 16:44

Knowledge of basic mathematical logic is, in my opinion, a plus. You can have a look at the two books by Cori and Lascar.

Mathematical Logic: A Course with Exercises Part I

Mathematical Logic: A Course with Exercises Part II

I recommend taking a look at these books:

Also, topics in the MFCS (Mathematical Foundations of Computer Science) conference might lead you to what kind of background you may need. (Caveat: the conference includes highly advanced topics. You don't need to master them. Just try to get the big picture.)

Number theory has not been mentioned, but it's a very important tool for many cryptographic and complexity-theoretic constructions.

Representation theory of finite groups (also over finite fields) can be surprisingly useful for various tasks, including:

• matrix multiplication algorithms (Cohn--Kleinberg-Szegedy-Umans)

• constructing locally decodable codes (see e.g. this paper by Klim Efremenko)

• applications in quantum computing (Hidden Subgroup Problem for nonabelian groups, multiplicative adversary method)

Although, to be honest, representation theory at the level required above can be learnt in two evenings (maybe three, if you want to learn representation theory of the symmetric group $S_n$), so there should be no pressure to learn it in advance.

• don't forget deterministic constructions of expander graphs – Sasho Nikolov Feb 17 '12 at 21:52
• You mean algebraic constructions using property (T) a la Lubotzky? In that case, this of somewhat different flavor than the examples above (don't use irreps of finite groups). – Marcin Kotowski Feb 18 '12 at 0:24

I recommend reading Garey and Johnson's book

Computers and Intractability: A Guide to the Theory of NP-Completeness.

This can be read with very little mathematical background. I think this book is a joy to read, and I would recommend it as a first book over Papadimitriou and Arora/Barak. Once you've read this, you can dip into the other books and identify various bits of mathematics you need to understand the advanced topics you are interested in.

• I learned complexity from this book, but find it unbalanced, with a lot of fiddly but ultimately unimportant details, yet it lacks coverage of issues that were important even at the time the book was written. On the other hand, it is occasionally an important reference work. In contrast, Kozen's text mentioned in another answer is clear, comprehensive and modern. – András Salamon Feb 17 '12 at 15:01

Once upon a time the undergraduate level course CS464 (2002) at UWaterloo CS used Christos H. Papadimitriou's Computational Complexity, Addison-Wesley, 1994.

Background topics listed include Turing machines, undecidability, time complexity, and NP-completeness.

For background, browse your library near QA267.G57 (Goddard's Introducing the theory of computation, based on a quick skim read or two and its availability to me, seems to cover the CS side of the background; I have a feeling some set and group theory from the pure math side would also be useful.)

• I wish I had enough reputation to vote down. Why those references to one university and its library? – Alessandro Cosentino Oct 31 '10 at 23:38
• FWIW, QA267.G57 is a Library of Congress call number, which is a widely used library standard. It is not specific to the University of Waterloo (except possibly for the final digits). – Emil Jeřábek Feb 17 '12 at 18:55