In Part 2 of this talk, we gave a crash course to graph theory and showed how we can use it to view some real-world problems as instances of the densest subgraph problem (DSP). But what exactly is the DSP? If you’ve studied graph theory, you may have heard of something called the Maximum Clique Problem. The goal of the max clique problem is to find the largest complete subgraph in a graph. If we consider our vertices to be people, and edges to represent a friendship relationship between two people, in the max clique problem we are trying to find the largest friend group in a community.

Simplicity and necessity: designs should be as simple and small as possible. Minimize functionality, favour minimal installs, and disable unused functionality. Aka: minimize the attack surface. Safe defaults: deny-by-default. Design systems to fail closed (denying access) and favour allowlists over denylists.

When we study computer and internet security (aka cybersecurity, in most circles), we are primarily interested in how people interact with software, computer systems, and networks, and in how they can be misused by various agents. We are typically not concerned with unintentional mistakes or other types of damages (such as a network failure cause by an outage or a natural disaster).

computer and Internet security: the combined art, science, and engineering practice of protecting software, computers, networks, the data stored on them, the information transmitted on/between them, and the physical devices/machines they control from intentional misuse by an unauthorized party.

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.