<blockquote>
<p>Is it reasonable to go into TCS research with little mathematical maturity and build it along the way?</p>
</blockquote>
<p>Yes, it's possible, but you need an advisor who's on board and you have to do a lot of work on building your mathematical maturity. And by the way, it's not just you; even many math majors often don't yet have the kind of mathematical experience and maturity that is really needed for research. Being good at problem-solving and proofs is a prerequisite, but not enough. (See <a href="https://terrytao.wordpress.com/career-advice/theres-more-to-mathematics-than-rigour-and-proofs/" rel="nofollow noreferrer">Terrence Tao's famous post</a>.)</p>
<p>An analogy I like is to being a professional musician. The foundation that you absolutely have to have are technical skills. But you want to master those well enough to use them, without consciously thinking about them, in a creative and high-level way.</p>
<p>So step 1 is mastering technical skills. Do math, especially proofs. For some reason, early in grad school, I was recommended a textbook (<a href="https://archive.org/details/elementsoftheory0000kolm_l7l2" rel="nofollow noreferrer">Kolmogorov and Fomin</a>) by another student and it just made advanced math &quot;click&quot; for me. I didn't really need the concepts for my research, but working through that short book really helped. Taking advanced, challenging proof-based math courses can be a better way to learn for early students than self-study.</p>
<p>Step 2 is getting practice using them in research, which is what a Ph.D. is for, so it's ok if you're not good at that yet. It takes a lot of practice. Break the math notation and pieces down very carefully and make sure you understand what they mean. Try to get an intuition for what is happening.</p>
<p>For example, let's look at Theorem 1.1 from the communication complexity monograph that you linked.</p>
<blockquote>
<p>Theorem 1.1 (Alon et al. 1999) Both <span class="math-container">$F_0$</span> and <span class="math-container">$F_2$</span> can be approximated, to within a <span class="math-container">$(1 \pm \epsilon)$</span> factor with probability at least <span class="math-container">$1 - \delta$</span>, in space <span class="math-container">$O(\epsilon^{-2} (\log n + \log m) \log \tfrac{1}{\delta})$</span>.</p>
</blockquote>
<p>Many things here are comfortable with experience but challenging to new students. What does it mean to approximate within a <span class="math-container">$(1 \pm \epsilon)$</span> factor with probability at least <span class="math-container">$1-\delta$</span>? Initially you have to think about this carefully, but after hundreds of times you take this sort of thing for granted and skim past it. In most of those hundreds of times, you would have seen that such accuracy guarantees often come with a number of samples like <span class="math-container">$\frac{1}{\epsilon^2} \log \tfrac{1}{\delta}$</span>, so you might not be surprised to see that number pop up.</p>
<p>So the new student will be trying to understand those details, while the more experienced researcher is wondering: Wow! Why is only <span class="math-container">$\log n + \log m$</span> space sufficient? This is what the discussion in the previous paragraphs focuses on. How do I count distinct elements without keeping track of exactly what I've already seen (which would take <span class="math-container">$\Theta(m \log(n))$</span> space? The <span class="math-container">$\epsilon$</span>s and <span class="math-container">$\delta$</span>s are distractions.</p>
<p>It is not easy to get to that point, but that's where you're headed: to be able to think intuitively about mathematical properties of a situation, and use math and rigor to support that thought process. My main advice is practice; hopefully others have more.</p>

CC BY-SA 4.0
2024-07-28T12:25:04.683Z
2024-07-30T06:21:52.417Z
2024-07-30T06:21:52.417Z
usul
<p>I have been involved in mentored research with a professor whose interests lie around randomness in computation. I was lost pretty much the entire time. I was reading <a href="https://arxiv.org/pdf/1509.06257" rel="noreferrer">material</a> at the graduate level with mathematics that just goes over my head. I have already taken the required discrete math course at my university and always do well in math classes.</p>
<p>Is it reasonable to go into TCS research with little mathematical maturity and build it along the way? How would this impact me if I were to pursue a PhD in this field? Or is that something only math majors would do?</p>

CC BY-SA 4.0
2024-07-27T04:15:36.957Z
you should major in math
mathworker21
CC BY-SA 4.0
2024-07-27T09:35:22.923Z
In my opinion, this really depends on the subarea of TCS that you want to study. I did my PhD in parameterized algorithms for graph problems with a major in bioinformatics. Concerning your experience with mentored research, I would say this also depends on the speed of the professor. Maybe a question to ask yourself is: Is there anything about TCS that you find particularly interesting? Why are you thinking about choosing TCS in the first place?
Christian Komusiewicz
CC BY-SA 4.0
2024-07-27T17:07:42.830Z
The trick is to understand that it's not always serious if you don't understand the proofs of everything. When you want to prove something you figure out what to do. Sometimes when you're given the proofs out of the blue it's hard to figure out the intuitive path behind it. Personally I've never made intuitive sense of Chernov's bound and it's been complex of mine, but it turns out it's never hindered me in TCS even in fields using randomness (or I don't know maybe it has ??)
ULechine
<advice-request>
How to develop mathematical maturity required for TCS research as a computer science major?
Excalibur
# How to develop mathematical maturity required for TCS research as a computer science major?

(Asked by: username_0 on 2024-07-26)

I have been involved in mentored research with a professor whose interests lie around randomness in computation. I was lost pretty much the entire time. I was reading [material](https://arxiv.org/pdf/1509.06257) at the graduate level with mathematics that just goes over my head. I have already taken the required discrete math course at my university and always do well in math classes.

Is it reasonable to go into TCS research with little mathematical maturity and build it along the way? How would this impact me if I were to pursue a PhD in this field? Or is that something only math majors would do?

**Tags:** advice-request
> **Comments:**
> **username_1**: you should major in math  
> **username_2**: In my opinion, this really depends on the subarea of TCS that you want to study. I did my PhD in parameterized algorithms for graph problems with a major in bioinformatics. Concerning your experience with mentored research, I would say this also depends on the speed of the professor. Maybe a question to ask yourself is: Is there anything about TCS that you find particularly interesting? Why are you thinking about choosing TCS in the first place?  
> **username_3**: The trick is to understand that it's not always serious if you don't understand the proofs of everything. When you want to prove something you figure out what to do. Sometimes when you're given the proofs out of the blue it's hard to figure out the intuitive path behind it. Personally I've never made intuitive sense of Chernov's bound and it's been complex of mine, but it turns out it's never hindered me in TCS even in fields using randomness (or I don't know maybe it has ??)  

---

## 1 answers

### Answer by username_4 on 2024-07-28. Score: 11 | Accepted answer

> Is it reasonable to go into TCS research with little mathematical maturity and build it along the way?

Yes, it's possible, but you need an advisor who's on board and you have to do a lot of work on building your mathematical maturity. And by the way, it's not just you; even many math majors often don't yet have the kind of mathematical experience and maturity that is really needed for research. Being good at problem-solving and proofs is a prerequisite, but not enough. (See [Terrence Tao's famous post](https://terrytao.wordpress.com/career-advice/theres-more-to-mathematics-than-rigour-and-proofs/).)

An analogy I like is to being a professional musician. The foundation that you absolutely have to have are technical skills. But you want to master those well enough to use them, without consciously thinking about them, in a creative and high-level way.

So step 1 is mastering technical skills. Do math, especially proofs. For some reason, early in grad school, I was recommended a textbook ([Kolmogorov and Fomin](https://archive.org/details/elementsoftheory0000kolm_l7l2)) by another student and it just made advanced math "click" for me. I didn't really need the concepts for my research, but working through that short book really helped. Taking advanced, challenging proof-based math courses can be a better way to learn for early students than self-study.

Step 2 is getting practice using them in research, which is what a Ph.D. is for, so it's ok if you're not good at that yet. It takes a lot of practice. Break the math notation and pieces down very carefully and make sure you understand what they mean. Try to get an intuition for what is happening.

For example, let's look at Theorem 1.1 from the communication complexity monograph that you linked.

> Theorem 1.1 (Alon et al. 1999) Both $F\_0$ and $F\_2$ can be approximated, to within a $(1 \pm \epsilon)$ factor with probability at least $1 - \delta$, in space $O(\epsilon^{-2} (\log n + \log m) \log \tfrac{1}{\delta})$.

Many things here are comfortable with experience but challenging to new students. What does it mean to approximate within a $(1 \pm \epsilon)$ factor with probability at least $1-\delta$? Initially you have to think about this carefully, but after hundreds of times you take this sort of thing for granted and skim past it. In most of those hundreds of times, you would have seen that such accuracy guarantees often come with a number of samples like $\frac{1}{\epsilon^2} \log \tfrac{1}{\delta}$, so you might not be surprised to see that number pop up.

So the new student will be trying to understand those details, while the more experienced researcher is wondering: Wow! Why is only $\log n + \log m$ space sufficient? This is what the discussion in the previous paragraphs focuses on. How do I count distinct elements without keeping track of exactly what I've already seen (which would take $\Theta(m \log(n))$ space? The $\epsilon$s and $\delta$s are distractions.

It is not easy to get to that point, but that's where you're headed: to be able to think intuitively about mathematical properties of a situation, and use math and rigor to support that thought process. My main advice is practice; hopefully others have more.


---

