A while ago, someone in a Discord server I’m in asked how much of the math behind a system you need to know to implement it. I thought it was an interesting question, and I felt qualified to answer it, so I ended up writing quite a lengthy response. It just occurred to me that it might also be useful to other people, so I thought I would clean it up a little bit and archive it here.

In the first part of this talk, I made the case that theory is useful because it allows us to find (or at the very least, have the correct toolkit and language to explore) solutions to real-world problems. In this part, we are going to look at some examples of such problems and develop mathematical language to be able to discuss them more abstractly. I’ve put the term “real-world” in quotes in the title, because I’m going to be talking about these problems in a lot of generality. However, I want to stress that specific instances of these problems are actually relevant in industry, and I think it’ll be easy to see why once I start talking about them.

Last summer, I spent a good chunk of my time doing an undergraduate research project during which I worked on a project largely by myself, under the supervision of a math professor. I then took a graduate level course in a related area this fall, where I investigated the theoretical underpinning behind my summer project. I had no idea what I was doing or what I had gotten myself into. As a result, I learned a lot, and tried to keep note of the various things I had learned. This is the first installment, on what I learned from trying to read math and theoretical CS papers.

If you’re a computer science student, you probably had to take an introductory discrete math course at some point. Did you enjoy it? If so, this talk probably isn’t for you, so you can feel free to skip the rest. (Or not – hopefully you feel like you can still learn something from me!) Jokes aside, it’s actually okay not to enjoy your intro to discrete math course: like, personally, I loved mine, but I also completely hated my discrete probability course and would prefer never to see it again. But I pick on discrete math because I feel like if it’s taught well, it can be a turning point for many people, and it certainly was for me.

While all NP-hard optimization problems are identical in terms of exact solvability, they may differ wildly from the approximative point of view. If the goal is to obtain an answer that is “good enough”, some problems become much easier (such as KNAPSACK), while others (such as CLIQUE) remain extremely hard.