Five motivations for theoretical computer science
February 28, 2015 9 Comments
There are some situations, perhaps lucky ones, where it is felt that an activity needs no external motivation or justification. For the rest, it can be helpful to think of what the task at hand can be useful for. This of course doesn’t answer the larger question of what is worth doing, since it just distributes the burden somewhere else, but establishing these connections seems like a natural part of an answer to the larger question.
Along those lines, the following are five intellectual areas for whose study theoretical computer science concepts and their development can be useful – therefore, a curiosity about these areas can provide some motivation for learning about those cstheory concepts or developing them. They are arranged from the likely more obvious to most people to the less so: technology, mathematics, science, society, and philosophy. This post could also serve as an homage to delayed gratification (perhaps with some procrastination mixed in), having been finally written up more than three years after first discussing it with Artem.
For the purposes of this post, the demarcation of what concepts and works are considered cstheory is a social one, based on them being such that most of their practitioners identify them as cstheory. This is not a result of going around asking the practitioners of the actual work being cited, but taking as a proxy publication venues and wikipedia categories, plus memories from my conversations within the context of the computer science community that signaled who considered their work part of cstheory. For example, in the case of bioinformatics the actual work seems not to be considered as cstheory by their practitioners, but if a piece of bioinformatics work was making heavy use of cstheory concepts then it would make sense to cite it within the context of the post as an example of a reason to care about cstheory if you care about biology. Artem’s potential disagreement notwithstanding.
Without any further ado, here are the five motivations:
- implementation of this work on fault tolerance, that led to improved performance of cloud storage in Microsoft, saving them millions of dollars. Historically speaking, the use of combinatorial algorithms (e.g. for matching) and the corresponding models within operations research can be classified here as well. Technology: The use of efficient or accurate algorithms can lead a company to make more money or offer a better product. A recent example is the
- Mathematics: Theoretical computer science is a continuous source of problems about mathematical structures pre-existing the cstheory concepts. This is because it is often the case that cstheory theorems will be easily reducible to a statement about the asymptotic behavior of such a mathematical structure. This can then make work on cstheory interesting to someone with an interest in the study of the corresponding mathematical structures. For example, there are several lines of work that often lead to problems in extremal combinatorics about expander graphs. Also, questions in quantum computing are often reducible to a problem regarding the asymptotic behavior of a particular family of matrices. This is the case in the work in communication complexity through looking at the norms of matrices representing the structure of the problem. It also happens in the study of XOR games through looking at the value of the Grothendieck constant for different dimensions (see Briët, Buhrman, & Toner, 2009).
these posts from the archive of TheEGG. Some of the techniques mentioned there are the use of complexity classes or properties of simplex algorithms to formalize intuitions about the behavior in certain fitness landscape models (Kaznatcheev, 2013), or
Barton, Novak, & Paxao (2014) connecting the diversity of alleles with the multiplicative-weights update algorithm (for an overview of MWU, see Arora, Barak, & Kale, 2012).
Science: This probably won’t require much commentary for the regular readers of this blog, since in fact it might be its main topic. But let us just say that it is hardly surprising that theoretical computer science can be used to systematize the study of processes with very relevant discrete steps and some order to their changes, such as evolution. See for example
- Society: The use of cstheory concepts has been useful in the analysis of societal structures and behavior. In the case of financial structures, Arora, S., Barak, B., Brunnermeier, M., & Ge, R. (2011) studied financial derivatives and questioned some often made assumptions on their effects in market efficiency, as already discussed in this blog. The concept that is used to justify the claim is the one of hardness through reduction. There is also work on the analysis of non-financial networks like Kleinberg (2000) that filters connection models for the small-world phenomenon by looking at how well decentralized path-making algorithms perform in them. The answers to these questions in stack overflow include pointers to other work along these lines.
- Philosophy: It feels natural to look at theoretical computer science as a sort of quantitative philosophy. This is because one of the foundations of the topic is offering mathematically rigorous models of processes, interactions and models themselves. It’s possible then to use mathematical tools to obtain answers to philosophical questions about these entities. A recent example is Aaronson’s (2013) work on the free will problem, where the no-cloning theorem from quantum computing plays a key role and other cstheory concepts like Kolmogorov complexity appear as well. See also this post from TheEGG archives that applies a cstheory perspective to the philosophy of science, using concepts like the lambda calculus, weighted automata and computational learning.
The examples within each category are of course not at all comprehensive – someone with a different taste or experience regarding cstheory work might suggest a completely different set. There also are of course plenty of lines of work that are helpful in the mentioned areas, and categorized by their practitioners under the label of computer science, but not under the one of cstheory. On top of the example of bioinformatics given in the introduction, there are also cases like work in operating systems in the case of technology, and the use of computers for simulations in the case of the study of societies.
Feel free then to add in the comments any examples that would be interesting to other readers! Or any other great examples of interdisciplinarity, really, they are always appreciated here.
Aaronson, S. (2013). The Ghost in the Quantum Turing Machine. arXiv:1306.0159.
Arora, S., Barak, B., Brunnermeier, M., & Ge, R. (2011). Computational complexity and information asymmetry in financial products. Communications of the ACM, 54(5): 101-107. Early version (2010) in Innovations in Computer Science.
Arora, S., Hazan, E., & Kale, S. (2012). The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 8(1): 121-164.
Barton, N.H., Novak, S., & Paixão, T. (2014). Diverse forms of selection in evolution and computer science. Proceedings of the National Academy of Sciences of the United States of America, 111 (29), 10398-9 PMID: 25009183
Briët, J., Buhrman, H., & Toner, B. (2009). A generalized Grothendieck inequality and entanglement in XOR games. arXiv preprint arXiv:0901.2009.
Easley, D., & Kleinberg, J. (2010). Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press.
Kaznatcheev, A. (2013). Complexity of evolutionary equilibria in static fitness landscapes. arXiv: 1308.5094v1
Kleinberg, J. (2000). The small-world phenomenon: An algorithmic perspective. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC) (pp. 163-170). ACM.