# What is the importance of a TCS researcher in a mostly applied CS department?

Stating the title in another way, how to convince a strong applied CS department that a theorist would be a better choice than one more applied computer scientist?

I understand that it is natural for a applied department to want one more expert on a specific field. On the other hand, diversity is important and I think the importance of a theorist goes beyond better theory courses.

What is the importance of a TCS researcher in a mostly applied CS department?

• Is this a department in the US ? There are funding-related reasons, but these reasons wouldn't apply outside the US. – Suresh Venkat May 29 '13 at 16:24
• I'm not in the US, and I was interested in the academic point of view, i.e. how a TCS researcher would increase the average quality (and maybe quantity) of research of such a department. The only reason I can think of is related to attracting students interested in theory. – Vinicius dos Santos May 29 '13 at 17:06
• Sometimes theory researchers can actually help applied researchers by coming up with better algorithms for their problems. You need the right kind of theorists and of applied computer scientists to get this kind of interaction, though. – Peter Shor May 29 '13 at 17:13
• theres some bias in both the question and audience! a broader question might be "what are suitable conditions/sitations" to introduce a theorist into a more applied arena. there it would largely depend on the area of CS under study, whether the applied approaches are running into inherent limits which the theory seems to answer, etc. – vzn May 30 '13 at 19:06

I am really not qualified to give an informed answer to your question, but there are many reasons for which a theory-oriented researcher might be a good fit for a more applied environment.

The main reason that comes to mind is this: good theoretic foundations are invaluable for a thorough understanding of an application which in turn increases trust, efficiency and decreases mental effort. In general it allows work to proceed much faster, as the foundations provide a mental reference that can be easily extended or made explicit.

I'm sure there are many examples in complexity theory, where an abstract approach has led to fantastic practical improvements in concrete implementations, but the field I am the most familiar with is "theory B", in which programing language design has greatly benefited from advances in pure computing theory research.

Haskell is a particularly good example. On the theory side, we have simple core languages like system $\mathrm{F}_\omega$ which have proven to be a very useful base for the core language of the GHC compiler. The research in type inference/reconstruction and more recently, on dependent types has guided the foundations of the Haskell design, including the Hindley-Milner architecture and GADTs. Monads, of course, were introduced in the from the most abstract domain of mathematics to the computing world by Moggi, a theorist.

More pragmatically, knowledge of the theory of operational semantics turns out to be an invaluable tool for language extensions: the paper which introduces Software Transactional Memory in Haskell has explicit operational semantics for the small sub-language containing the STM constructs. This creates a reference for the implementation, and the ability to prove properties about a correct implementation, creating trust and understanding.

All this point to the fact that having a strong theory background is an important asset of every research team, including those with a strong application theme.

In addition to the points given in the other answers, I think any CS department offering an Undergraduate programme must have a reasonable number of faculty from the various CS communities, irrespective of what its broad leanings. Otherwise, a new student joining the department would naturally get aligned with the departments focus, without much of a choice. An applied professor may be able to teach TCS courses (and vice-verse), but would be unlikely to be able to pique the student's interest in the same.

heres another angle on this. the question starts out with an a priori "hard sell" situation/case ie a dept that is mostly applied is already going to have an inherent bias against a more theoretical researcher, otherwise that researcher would already be in the dept.

one possible direction "in" is the following. an often overlooked area of software development/design in industry and sometimes computer science departments is architecture. sometimes even TCS does not have large awareness of architecture either, but it is better positioned to recognize it than with applied focus.

in a few words, software architecture is the study of complexity in the solution/software, and ways of minimizing it, which is a major issue esp. with large software projects, which these days are increasingly more common.

software architecture involves in part the choice of algorithms (ie choice among equivalent algorithms, in terms of input/output relationship, based on different performance and scalability characteristics). sometimes applied workers are not even familiar with the basic theory that tells you stuff like an indexed column on a database is $O(log(n))$ access time instead of $O(n)$ and why this is in fact a "big deal". architecture is also tied with very practical topics like when refactoring of code is appropriate or not.

also it seems like some complex commercial software has many dimensions of scalability. in robotics an analogous concept is "degrees of freedom". the software scales in many separate dimensions. for example, memory size, size of web pages, size of database results, etcetera. a good theoretical researcher will be able to more systematically/scientifically assist in identifying and quantifying all these dimensions, ie using the scientific method. more applied workers will tend to just resort to trial and error, sometimes over a period of years, never really understanding exactly why their software is underperforming, hitting internal ceilings, or failing.

there are a few rare researchers who can cross between theory and applied realms without difficulty, or as the vernacular goes, "feet in both worlds". maybe studying them in particular (their career directions and writing, etc) will help to develop the mindset and philosophy to "cross over". in particular, Grady Booch is one eminent figure who comes to mind. he invented much of the concepts behind OOP programming and has much excellent research/writing on the topic of software architecture. another similar researcher is Phillip Kruchten. and yes [as in comments], Peter Shor.

having worked with both, one possible distinction is that in a more applied setting the main deliverable is code and in a more theoretical setting the "deliverables" are analyses/paper(s). this can cause a cultural gap if not everyone is "on the same page" with what are the deliverables. in this case the theoretical scientist will be the one who will have to bend & be more flexible and also "be ok" with that. so the personality of this key person will be a key factor.

another emerging/very prominent area these days that has strong interdisciplinary connection/overlap between theoretical and applied scientists is datamining, reaching larger prominence with official government/corporate initiatives into big data (and again architecture is a foremost element in this).

• Pardon me. I fail to understand why so many downvotes. It seems to be a reasonable answer. Downvoters please provide reasons so that others may learn from you. – scaaahu Jun 7 '13 at 3:34
• I think the idea that software architecture is or should be a subarea of theoretical computer science would be considered very insulting by some people who actually do software research in computer architecture. If you're trying to make a case for why a department should hire you, one of the first rules is don't insult them. – Peter Shor Sep 23 '14 at 18:52
• @Peter there is no denigration intended, implied, or expressed above to anyone. not following your apparent objection. agreed software architecture is now regarded very/highly applied (apparently your main point), but historically it was very abstract in various ways eg OOP and seems started out roughly in near-research labs as "TCS" in a somewhat informal sense of "not actually used in industry" (to begin with). – vzn Sep 23 '14 at 21:21
• Do you think that telling a software architecture expert that "an often overlooked area of software development/design in industry and sometimes computer science departments is architecture" and then explaining that somebody from theoretical computer science "is better positioned" to help with his field than somebody "with applied focus" isn't insulting? Or did you actually mean something else? – Peter Shor Sep 23 '14 at 23:44
• spking from experience in industry, there is a tendency toward what one CS prof called "pseudopodic design" where there is a lack of overall coherent architecture and the software grows organically/ somewhat haphazardly like pseudopods shooting from an amoeba. there are those with very applied focus that build these systems often under intense schedule pressure & architecture attn can be seen as a luxury or worse/ inaccurately, superfluous. Booch with much experience describes these environments as "circles of hell". a theoretical bkg/ edu eg Phd can naturally counteract this shortsightedness. – vzn Sep 24 '14 at 4:42