Five motivations for theoretical computer science

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:

  • Turing Machine

    Finite approximation to Turing machine

    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 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.
  • 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).
  • fitness landscape

    Visualization of 2-dimensional NK-fitness landscape by Randy Olson.

    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 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).
  • 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.

References

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.

Advertisements

About Abel Molina
Abel Molina does research - mostly in quantum information and quantum computation, and mostly at the Institute for Quantum Computing, University of Waterloo. He was also part of the team for the location-based social-networking Highlight app. If you like this, you might be able to find more that you like at @exexist in English, and in Spanish at @exexist_es.

9 Responses to Five motivations for theoretical computer science

  1. Pingback: Five motivations for theoretical computer science | Sublime Illusions

  2. Quanquan Liu says:

    Reblogged this on Sublime Illusions and commented:
    This is an interesting blog post about some perceived motivations behind CS Theory. Although I don’t one hundred percent agree with the idea that CS Theory needs motivation from other science areas (the same reason why I think research in pure math doesn’t need motivation), it’s a good read and makes good points.

    • I am not sure if Abel is saying that cstheory needs motivations external to itself — at least I know that I would not say that — as much as “if you want some motivations that are external then here are some”. But I do think there is some danger in being too self-motivating in that it often results in building a wall around your field and not integrating with the rest of knowledge and wonder; this makes life a bit more boring compared to the well-integrated position of being able to see glimpses of the things you love wherever you look.

      • Quanquan Liu says:

        I certainly love hearing about the applications of theoretical computer science and mathematics to other science areas. I am personally curious about evolutionary game theory, especially its applications in cancer research (hence the reason I follow this blog). So my comment was definitely not directed towards the idea that research should be entirely self-motivated.

        The reason for my disclaimer was that I wanted to ward against interpreting the blog post as “cstheory has useful applications, therefore, it is worth studying.” Cstheory has useful applications, and I am tremendously interested in those applications, but the field itself also has its own merit outside of these applications. Looking at the blog post again, I don’t think it is saying my above quote (and as I mentioned before, it is a very good read), but one sometimes have to be careful with similar blog posts about applications of theoretical research fields.

        • Abel Molina says:

          Yeah, the topic of “motivation by connection with another area” definitely seems of some interest independently of whether one considers they are necessary or not – which can also be examined at different levels, from ‘should I still plan to spend my time on cstheory even if these external motivations didn’t exist’, to ‘should money from taxpayers of a particular area be spent on cstheory even if these external motivations didn’t exist’.

          Personally I wouldn’t defend any strong views about the topic, and don’t feel very compelled to proselytize about it, unlike the topic of whether those external motivations exist at all, and what are they like : )

  3. Pingback: An update | Theory, Evolution, and Games Group

  4. vznvzn says:

    kind of a dark age, or at least a gray age, when one has to justify science :!:

    and (T)CS is one of the most interesting emerging scientific fields in existence. re technology/ society, other stuff: social networking & ubiquitous smartphones/ apps (soon/ quickly to bring computers to the unnetworked 3rd world, bringing along other advances like finance)…. bitcoin… study of complex systems, emergence, nonreductionistic science, robotics, big data, artificial intelligence etc! the list is very long! & as mentioned, algorithmic lens! 21st century may be the century that computers get into 5th gear after being only in 1st 2nd 3rd so far… much more in my blog…. maybe need to write a post like this one some time! also this post shows connections of TCS with deep math etc

  5. Pingback: Five motivations for theoretical computer science | Rupei Xu

  6. Pingback: Cataloging a year of blogging | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s