In this video we look at a different computational model related to an important social concern about how to fairly allocate divisible resources under some constraints. There are a couple of goals of this. First, it provides a completely new model of computation with its own rules on what counts a computational step and what the input length is. As such, we hope that this will expand your horizon on what we can view as a computational process, and how we can measure its complexity. Second, this topic illustrates one of the many real-world applications of theoretical computer science. Finding fair ways of dividing limited resources is very important, and studying this problem mathematically rigorously provides provable solutions. See the following for examples of the applications:
For a great introduction to the area of computational social choice theory, please see http://procaccia.info/wp-content/uploads/2020/03/4centuries.pdf. The article contains the history and motivations surrounding computational social choice, which has important implications on our daily lives. For example, we use elections to choose our political leaders, and the voting rules we use in these elections can have dramatic effects on the potential outcomes.
Our goal in this video is two-fold. First, we would like to show you that the important area of collective decision making, which at first seems to have nothing to do with computer science, can be studied in the context of theoretical computer science. This allows us to generate very interesting results and insights, which can then be used to implement provably better decision making systems (e.g. elections). Second, the study of computational social choice has interesting ties to the theory of \(\mathsf{NP}\)-hardness. Even though in many settings, the hardness of a computational problem is viewed as a negative thing, it turns out that in certain settings, the hardness of certain problems can be very desirable. Computational social choice happens to be one of those settings where computational hardness can be desirable, and we will see one such example.
Algorithmic game theory is at the intersection of computer science and economics. In a broad sense, game theory studies the strategic interactions among a number of rational participants. This of course encapsulates a lot of different and important scenarios. In this video we look at some formalizations and examples.
Machine learning is currently one of the hottest areas in computer science. In this video we look at one formal modal for learning which gives us very nice tools to rigorously reason about it.
In the chapter on modular arithmetic, we saw that \(\mathbb{Z}_N\) together with the addition operation \(+_N\) is a universe that behaves “nicely” (e.g. we have a unique additive identity and every element has an additive inverse, which allows us to define a minus operation). On the other hand, \(\mathbb{Z}_N\) does not behave nicely with respect to the operation \(\cdot_N\). Therefore, we looked at the subset \(\mathbb{Z}_N^*\) which behaves nicely with respect to \(\cdot_N\). In this chapter, we abstract away these concepts and precisely define what it means for a set, together with an operation defined on that set, to be “nice” and have qualities that are desirable. These objects are known as groups and there is a big area in mathematics called group theory that studies such objects in detail.
These abstractions are extremely valuable and allows mathematicians to reason about fundamental truths about sets with well-behaved operations. In computer science it is common to use these abstract constructs in applications such as cryptography.
Polynomials are primary tools in the toolkit of a theoretical computer scientist and have various important applications in computer science (e.g. in error-correcting codes, interactive proofs, and communication complexity). In this video, after introducing polynomials and their basic properties, we present an application in the error-correcting codes. Error-correction is essential in many settings because the environment inevitably introduces errors (it is crucial to quantum computation as well). We would like to successfully carry out computational and communicational tasks even in the presence of errors and noise. The field of error-correcting codes gives us a rich set of tools to accomplish this. One simple example is a QR code, which is a matrix bar code. They use Reed-Solomon error-correction, which is the highlight of this section.
This previous section is a prerequisite for this section.
What is a proof? One can say that this question, and the attempt to formalize the concept of a proof has led to the birth of computer science. Computer science has returned the favor by completely changing how we think about proofs. It has introduced the concepts of interactive proofs, zero-knowledge proofs, spot-checkable proofs, etc. In this video we give a broad overview of these concepts which are not only important from a theoretical standpoint, but also have very interesting applications, e.g., in blockchains and authentication systems.
This is a TCS story you don’t want to miss. A “simple” problem like Max-Cut reveals beautiful connections with math and science.