Hello, Codeforces Community!
Since my middle school days, I've been deeply involved in Olympiad Informatics, which sparked my passion for algorithms and data structures. Now, as a first-year computer science undergraduate, my ambition is to pursue a career in theoretical computer science (TCS) research.
I would greatly appreciate any advice from those currently engaged in TCS or combinatorial optimization research.
TCS research isn't really much like CP at all IMO; almost all of the classical algorithms research is kinda "done", in the sense that it's hard to do impactful work (old fields have a lot less "low hanging fruit", so you'd spend a lot of time working on a relatively incremental result vs. working on newer problems). There's a recent trend of "algorithms with advice" which is augmenting classical algorithms with ML, which is one trendy area which is similar to classical data structures and algorithms. I can't really say how long that will last though, if you're looking to make a career out of it.
Generally for TCS, build a strong background in math and proofs. Probably also take a look at quantum, as there are 1e9 emerging problems in quantum, so surely one of them will catch your eye.
How smart (in terms of raw intellect/mathematical ability, which I think correlate highly positively with CF rating) do you think one needs to generally be to do meaningful research?
I often feel like research in computer science is something I would find extremely enjoyable and want to pursue. But then I remind myself that I am vastly cognitively inferior to so many people in the same field (for example chinese high-school CPers) who could do anything I could do, in a better manner and in less time.
Useless question. Does the existence of someone smarter than you mean than you shouldn't do anything meaningful with your life?
If you can build the math background you need to understand the problems and techniques people use in TCS, you can probably make a dent in something.
Useless response. Yes.
My experience was the exact opposite. I made some minor progress towards a somewhat-obscure open problem and a friend made improvements on some open problems in stuff very adjacent to classical algorithms. It's very similar to competitive programming.
My experience was also the exact opposite here. It was impossibly difficult for me (skill issue perhaps) and radically different from competitive programming. I met with people who worked on quantum computing for years in PhD and told me it's not going anywhere in a few decades. I recently learned no factorization of any number larger than 21 has been carried out with an algorithm scalable to modern encryption on a quantum computer, and even that was a gimmick (though recently there was some factorization of a 48-bit number with an algorithm that does not scale). To me it seems that 12 years have passed since 21 got factored and nothing has happened. It all just sounds like fake news after seeing "quantum computers are going to break encryption in 10 years" since I was in middle school.
Perhaps I stand corrected on the frequency CP-like problems in TCS; this is just my perspective from the problems I've worked on and from what I've seen at conferences. It feels like there is much more room for interesting proof techniques as opposed to interesting algorithm design (which I suppose you can argue is the same thing, a la Curry-Howard).
I agree that if you look at quantum expecting to speed up classical computing, you will be disappointed. I also agree with the "fake news" feeling of quantum, which is similar to the "string theory will change the world" story that I kept hearing growing up. I think the more interesting questions come from quantum information science (with applications in physics and chemistry), as opposed to "how do we solve X classical problem with quantum?".
The problems I saw were mostly presented during some graduate algorithm classes. Maybe they were picked because they were thought to be more accessible, or because they weren't well studied? But certainly the results were new to the professors, made meaningful improvements, and were not some random "we improved the runtime by $$$n^{0.002}$$$" silliness (though in my case it wasn't enough to publish anything; I only thought about it for about 8 hours and did not manage to fully resolve one final case so perhaps it was trivial). I know that in those classes students published new research before.