<p>This might be an unusual question, but please bear with me. As a graduate student in mathematics, I haven't delved deeply into several discrete math subjects relevant to research in theoretical computer science. I am keen to address this deficiency with the intention of learning discrete math topics and techniques for research motivated by the following topics:</p>
<ul>
<li><p>I am interested in various statistical complexity measures such as VC dimension and Rademacher complexity. I am interested in learning about techniques to prove lower and upper bounds. Perhaps subjects like extremal combinatorics are relevant here.</p>
</li>
<li><p>A lot of constructions in classical and quantum coding theory are inspired by graph theory (expander codes, codes over finite fields). I am interested in learning several discrete math topics that are relevant here.</p>
</li>
</ul>
<p>I am looking for recommendations for books and papers where I can learn the necessary discrete math and techniques regarding my research interests.</p>

CC BY-SA 4.0
2024-02-15T02:33:10.367Z
Foundations of Data Science by Avrim Blum, John Hopcroft, and Ravindran Kannan
Shi
CC BY-SA 4.0
2024-02-15T14:03:55.647Z
I recall that somebody asked Andrew Yao something similar once, and his advice was to learn the math that you need for the particular TCS problem that you are interested in.  Presumably because you don't know in advance what kinds of math will be useful.  This is assuming you have a core background.  For many core topics there are PhD courses on those topics that give you basic background.  Possible exceptions (that you may need to study independently) include probability and probabilistic arguments and ways to handle sums and asymptotics beyond what is typically covered in a core class.
Neal Young
CC BY-SA 4.0
2024-02-17T03:23:43.593Z
It's a bit hard to tell the level of material you're thinking of. A standard undergrad text on Discrete Math is Rosen's. If you know all that stuff, then you're going in with similar knowledge to most first-year CS PhDs and I'd follow Neal Young's advice and jump into the relevant PhD-level CS course/book you're interested in.
usul
<reference-request>
Learning discrete math for research
user72031
# Learning discrete math for research

(Asked by: username_0 on 2024-02-14)

This might be an unusual question, but please bear with me. As a graduate student in mathematics, I haven't delved deeply into several discrete math subjects relevant to research in theoretical computer science. I am keen to address this deficiency with the intention of learning discrete math topics and techniques for research motivated by the following topics:

* I am interested in various statistical complexity measures such as VC dimension and Rademacher complexity. I am interested in learning about techniques to prove lower and upper bounds. Perhaps subjects like extremal combinatorics are relevant here.
* A lot of constructions in classical and quantum coding theory are inspired by graph theory (expander codes, codes over finite fields). I am interested in learning several discrete math topics that are relevant here.

I am looking for recommendations for books and papers where I can learn the necessary discrete math and techniques regarding my research interests.

**Tags:** reference-request

> **Comments:**
> **username_1**: Foundations of Data Science by Avrim Blum, John Hopcroft, and Ravindran Kannan  
> **username_2**: I recall that somebody asked Andrew Yao something similar once, and his advice was to learn the math that you need for the particular TCS problem that you are interested in.  Presumably because you don't know in advance what kinds of math will be useful.  This is assuming you have a core background.  For many core topics there are PhD courses on those topics that give you basic background.  Possible exceptions (that you may need to study independently) include probability and probabilistic arguments and ways to handle sums and asymptotics beyond what is typically covered in a core class.  
> **username_3**: It's a bit hard to tell the level of material you're thinking of. A standard undergrad text on Discrete Math is Rosen's. If you know all that stuff, then you're going in with similar knowledge to most first-year CS PhDs and I'd follow username_2's advice and jump into the relevant PhD-level CS course/book you're interested in.  

---

## 0 answers

