<p>You should add <a href="http://rads.stackoverflow.com/amzn/click/1846282977">Dexter Kozen's book</a> on the theory of computation to your list. Covers the basics of complexity theory very effectively, and the short lecture format is great. </p>

<p>In terms of mathematical background, in addition to what's mentioned above:</p>

<ul>
<li>Probability theory</li>
<li>Linear algebra and abstract algebra</li>
<li>graph theory</li>
<li>basic logic</li>
</ul>

<p>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. </p>

CC BY-SA 2.5
2010-10-31T06:37:46.747Z
2010-10-31T06:37:46.747Z
Suresh Venkat
<p>$\bullet$ The book <em>Extremal Combinatorics</em>, 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.</p>

<p>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:</p>

<p><a href="https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science" rel="noreferrer">https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science</a></p>

<p>$\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 <em>The Probabilistic Method.</em></p>

CC BY-SA 2.5
2010-10-31T21:28:27.540Z
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
CC BY-SA 3.0
2010-10-31T20:53:42.810Z
2015-11-15T17:26:08.947Z
2015-11-15T17:26:08.947Z
Andy Drucker
<p>The previous answers already listed the basic ones: probability theory, combinatorics, linear algebra, abstract algebra (finite fields, group theory, etc).</p>

<p>I would add: </p>

<p><strong>Fourier analysis</strong>, see, e.g., Ryan O'Donnel's course: 
<a href="http://www.cs.cmu.edu/~odonnell/boolean-analysis/">http://www.cs.cmu.edu/~odonnell/boolean-analysis/</a> </p>

<p><strong>Coding theory</strong>, see Madhu Sudan's course:
<a href="http://people.csail.mit.edu/madhu/coding/course.html">http://people.csail.mit.edu/madhu/coding/course.html</a></p>

<p><strong>Information theory</strong>, the standard book is Elements of Information Theory: <a href="http://rads.stackoverflow.com/amzn/click/0471241954">http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954</a></p>

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

CC BY-SA 2.5
2010-11-01T00:45:31.623Z
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
CC BY-SA 3.0
2010-10-31T18:55:10.883Z
2012-10-09T13:23:42.597Z
2012-10-09T13:23:42.597Z
Dana Moshkovitz
<p>Sanjeev Arora has <a href="http://www.cs.princeton.edu/~arora/pubs/toolkit.pdf">a nice document</a> 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.</p>

CC BY-SA 2.5
2010-11-01T00:50:00.470Z
2010-11-01T00:50:00.470Z
Lev Reyzin
<p>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. </p>

<p>"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.</p>

CC BY-SA 2.5
2010-10-31T23:10:42.017Z
2010-10-31T23:10:42.017Z
TCSgradstudent
<p>I think a list of fields of mathematics that are <em>not</em> useful would be much shorter than a list of fields that are!  I can't think of any.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-31T16:44:25.767Z
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
CC BY-SA 2.5
2010-10-31T16:17:25.187Z
2010-10-31T16:17:25.187Z
Jeffε
<p>Apart from basic stuff, probably:</p>

<ul>
<li><strong>Combinatorics</strong> -- You might find youself counting things quite regularly</li>
<li><strong>Stochastics</strong> -- For average case analyses and randomized algorithms</li>
</ul>

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

<p>If you like <strong>generating functions</strong> (see <em>generationfunctionology</em> by Wilf) as a tool, <strong>complex analysis</strong> comes in handy, too.</p>

CC BY-SA 2.5
2010-10-31T18:11:33.100Z
I love Concrete Math, but it is a bit esoteric. I would recommend a more mainstream book first, like Cameron's "Combinatorics".
Emil
CC BY-SA 2.5
2010-10-31T23:36:23.683Z
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
CC BY-SA 2.5
2010-10-31T23:39:28.797Z
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
CC BY-SA 2.5
2010-10-31T23:44:18.090Z
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
CC BY-SA 2.5
2010-10-31T05:29:08.090Z
2010-10-31T05:29:08.090Z
Raphael
<p>Knowledge of basic mathematical logic is, in my opinion, a plus. You can have a look at the two books by Cori and Lascar.</p>

<p><a href="http://books.google.com/books?id=Cle6_dOLt2IC&amp;dq=editions%3aCle6_dOLt2IC&amp;hl=en&amp;ei=-EHNTM7SBorMswbOuPCWCA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCUQ6AEwAA">Mathematical Logic: A Course with Exercises Part I</a></p>

<p><a href="http://books.google.com/books?id=zDrqGvJhSPIC&amp;printsec=frontcover&amp;dq=cori+lascar&amp;hl=en&amp;ei=0EHNTMa_BYqVswbXyfWWCA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCgQ6AEwAA#v=onepage&amp;q&amp;f=false">Mathematical Logic: A Course with Exercises Part II</a></p>

CC BY-SA 2.5
2010-10-31T10:17:25.663Z
2010-10-31T10:17:25.663Z
Sylvain Peyronnet
<p>I recommend taking a look at these books:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0691118809">The Princeton Companion to Mathematics</a></li>
<li><a href="http://rads.stackoverflow.com/amzn/click/052154310X">Logic in Computer Science; Modelling and Reasoning about Systems</a></li>
</ul>

<p>Also, topics in the <a href="http://www.informatik.uni-trier.de/~ley/db/conf/mfcs/">MFCS (Mathematical Foundations of Computer Science)</a> 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.)</p>

CC BY-SA 2.5
2010-10-31T16:42:05.463Z
2010-10-31T16:42:05.463Z
Sadeq Dousti
<p>Number theory has not been mentioned, but it's a very important tool for many cryptographic and complexity-theoretic constructions.</p>

CC BY-SA 2.5
2010-11-02T05:08:36.047Z
2010-11-02T05:08:36.047Z
arnab
<p>Representation theory of finite groups (also over finite fields) can be surprisingly useful for various tasks, including:</p>
<ul>
<li><p>matrix multiplication algorithms (<a href="http://users.cms.caltech.edu/%7Eumans/papers/CKSU05.pdf" rel="nofollow noreferrer">Cohn--Kleinberg-Szegedy-Umans</a>)</p>
</li>
<li><p>constructing locally decodable codes (see e.g. <a href="https://doi.org/10.1145/2213977.2214008" rel="nofollow noreferrer">this paper</a> by Klim Efremenko)</p>
</li>
<li><p>applications in quantum computing (Hidden Subgroup Problem for nonabelian groups, multiplicative adversary method)</p>
</li>
</ul>
<p>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 <span class="math-container">$S_n$</span>), so there should be no pressure to learn it in advance.</p>

CC BY-SA 3.0
2012-02-17T21:52:40.743Z
don't forget deterministic constructions of expander graphs
Sasho Nikolov
CC BY-SA 3.0
2012-02-18T00:24:16.673Z
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
CC BY-SA 4.0
2012-02-17T17:16:23.457Z
2021-12-01T22:56:52.367Z
2021-12-01T22:56:52.367Z
Marcin Kotowski
<p>I recommend reading Garey and Johnson's book</p>

<p><em>Computers and Intractability: A Guide to the Theory of NP-Completeness</em>.</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-17T15:01:45.813Z
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
CC BY-SA 2.5
2010-10-31T18:17:28.810Z
2010-10-31T18:17:28.810Z
Emil
<p>Once upon a time the undergraduate level course <a href="http://www.student.cs.uwaterloo.ca/~cs464/" rel="nofollow">CS464 (2002)</a> at UWaterloo CS used Christos H. Papadimitriou's <em>Computational Complexity</em>, Addison-Wesley, 1994.</p>

<p>Background topics listed include Turing machines, undecidability, time complexity, and NP-completeness.</p>

<p>For background, browse your library near QA267.G57 (Goddard's <em>Introducing the theory of computation</em>, 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.)</p>

CC BY-SA 3.0
2012-02-17T18:55:01.667Z
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
CC BY-SA 2.5
2010-10-31T23:38:52.907Z
I wish I had enough reputation to vote down. Why those references to one university and its library?
Alessandro Cosentino
CC BY-SA 2.5
2010-10-31T06:26:37.993Z
2010-10-31T06:26:37.993Z
josh0
<p>If you look at the answers to <a href="https://cstheory.stackexchange.com/questions/1920/examples-of-unrelated-mathematics-playing-a-fundamental-role-in-tcs">this TCS StackExchange question</a>, 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.</p>

CC BY-SA 2.5
2010-11-21T14:23:47.570Z
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 
CC BY-SA 2.5
2010-10-31T17:59:50.817Z
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 
CC BY-SA 2.5
2010-10-31T14:17:58.903Z
2010-10-31T21:22:24.420Z
2017-04-13T12:32:28.117Z
Peter Shor 
<p>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.</p>

<p>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.).</p>

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

CC BY-SA 4.0
2021-12-02T17:24:04.370Z
The original question was asked 11 years ago. I wonder if @chazisop ended up with a TCS Masters/PhD and found the replies here helpful.
Martin Berger
CC BY-SA 4.0
2021-12-03T14:30:59.390Z
Hello Martin, indeed it's been quite some time since I posed the question. I'm happy to say that I indeed hold a M.Sc. and expect to obtain my Ph.D. in Summer 2022 in Algebraic Complexity Theory. Peter Shor's answer, which I accepted, is really insightful, as well as the comment below it and I wouldn't hesitate to pass it on to students.

A good understanding of the basics will serve them well, but the need to deeply understand specialized topics seems to remain throughout one's career (as far as I can tell), since they appear naturally when studying various problems (or tools to solve them)
chazisop
CC BY-SA 2.5
2010-10-31T06:08:43.300Z
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
CC BY-SA 2.5
2010-10-31T16:18:19.740Z
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
<cc.complexity-theory><soft-question><advice-request>
What kind of mathematical background is needed for complexity theory?
chazisop
# What kind of mathematical background is needed for complexity theory?

(Asked by: username_0 on 2010-10-31)

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.

**Tags:** cc.complexity-theory, soft-question, advice-request
> **Comments:**
> **username_2**: 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.  
> **username_3**: 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.  
> **username_1**: The original question was asked 11 years ago. I wonder if @chazisop ended up with a TCS Masters/PhD and found the replies here helpful.  
> **username_0**: Hello Martin, indeed it's been quite some time since I posed the question. I'm happy to say that I indeed hold a M.Sc. and expect to obtain my Ph.D. in Summer 2022 in Algebraic Complexity Theory. Peter Shor's answer, which I accepted, is really insightful, as well as the comment below it and I wouldn't hesitate to pass it on to students.  A good understanding of the basics will serve them well, but the need to deeply understand specialized topics seems to remain throughout one's career (as far as I can tell), since they appear naturally when studying various problems (or tools to solve them)  

---

## 14 answers

### Answer by username_21 on 2010-10-31. Score: 57 | Accepted answer

If you look at the answers to [this TCS StackExchange question](https://cstheory.stackexchange.com/questions/1920/examples-of-unrelated-mathematics-playing-a-fundamental-role-in-tcs), 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.

> **Comments:**
> **username_21**: 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.  
> **username_21**: 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.  

---

### Answer by username_4 on 2010-10-31. Score: 37

You should add [Dexter Kozen's book](http://rads.stackoverflow.com/amzn/click/1846282977) 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.


---

### Answer by username_5 on 2010-10-31. Score: 35

$\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.*

> **Comments:**
> **username_6**: 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.  

---

### Answer by username_7 on 2010-10-31. Score: 30

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

I would add:

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

**Coding theory**, see Madhu Sudan's course:
<http://people.csail.mit.edu/madhu/coding/course.html>

**Information theory**, the standard book is Elements of Information Theory: [http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954](http://rads.stackoverflow.com/amzn/click/0471241954)

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

> **Comments:**
> **username_7**: 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.  

---

### Answer by username_12 on 2010-10-31. Score: 26

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.

> **Comments:**
> **username_13**: I love Concrete Math, but it is a bit esoteric. I would recommend a more mainstream book first, like Cameron's "Combinatorics".  
> **username_5**: 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.  
> **username_5**: 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.  
> **username_5**: 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.  

---

### Answer by username_8 on 2010-11-01. Score: 23

Sanjeev Arora has [a nice document](http://www.cs.princeton.edu/~arora/pubs/toolkit.pdf) 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.


---

### Answer by username_9 on 2010-10-31. Score: 20

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.


---

### Answer by username_10 on 2010-10-31. Score: 18

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.

> **Comments:**
> **username_11**: 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.  

---

### Answer by username_14 on 2010-10-31. Score: 14

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](http://books.google.com/books?id=Cle6_dOLt2IC&dq=editions%3aCle6_dOLt2IC&hl=en&ei=-EHNTM7SBorMswbOuPCWCA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCUQ6AEwAA)

[Mathematical Logic: A Course with Exercises Part II](http://books.google.com/books?id=zDrqGvJhSPIC&printsec=frontcover&dq=cori+lascar&hl=en&ei=0EHNTMa_BYqVswbXyfWWCA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCgQ6AEwAA#v=onepage&q&f=false)


---

### Answer by username_15 on 2010-10-31. Score: 13

I recommend taking a look at these books:

* [The Princeton Companion to Mathematics](http://rads.stackoverflow.com/amzn/click/0691118809)
* [Logic in Computer Science; Modelling and Reasoning about Systems](http://rads.stackoverflow.com/amzn/click/052154310X)

Also, topics in the [MFCS (Mathematical Foundations of Computer Science)](http://www.informatik.uni-trier.de/~ley/db/conf/mfcs/) 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.)


---

### Answer by username_6 on 2010-11-02. Score: 9

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


---

### Answer by username_16 on 2012-02-17. Score: 7

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

* matrix multiplication algorithms ([Cohn--Kleinberg-Szegedy-Umans](http://users.cms.caltech.edu/%7Eumans/papers/CKSU05.pdf))
* constructing locally decodable codes (see e.g. [this paper](https://doi.org/10.1145/2213977.2214008) 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.

> **Comments:**
> **username_17**: don't forget deterministic constructions of expander graphs  
> **username_16**: 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).  

---

### Answer by username_13 on 2010-10-31. Score: 4

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.

> **Comments:**
> **username_18**: 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.  

---

### Answer by username_19 on 2010-10-31. Score: 1

Once upon a time the undergraduate level course [CS464 (2002)](http://www.student.cs.uwaterloo.ca/~cs464/) 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.)

> **Comments:**
> **username_3**: I wish I had enough reputation to vote down. Why those references to one university and its library?  
> **username_20**: 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).  

---

