Dinner-table description of theoretical computer science?

I'm often asked what a theoretical computer scientist does. It would be great to have some nice responses to this question. I tend to fall back to technical jargon and people's eyes usually glaze over at this point.

What does a theoretical computer scientist do, in terms that can be understood by people who are not computer scientists?

A good answer should be snappy, accurate in spirit, without sounding vague or trite. For bonus points, the answer should hint at why a theoretical computer scientist is neither a mathematician nor an IT practitioner.

This question is inspired by the MO question https://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics although the intent is different.

My response is generally, "I study why some computations are hard to do". As an example, I typically compare addition and multiplication using the standard grade school methods. These are computations that everyone has done and that everyone appreciates the value of doing quickly. Everyone agrees that for large numbers, multiplication is much harder than addition. In fact, most people suggest that the elementary school method is as fast as you can go. Then I ask them why. How do they know that there isn't another way to do multiplication that is just as easy as addition?

Pretty much everyone has at least some appreciation at this point for the difficulty of proving lower bounds (my particular interest), even though I haven't used that term. Depending on the background and interest of the audience, I may mention that someone has found a way to multiply that is much faster than the elementary school method (simply the word "algorithm" tends to bring a glaze to their eyes), but still slower than adding.

• I like that your example uses addition and multiplication as examples. It seems these would somehow be even less intimidating to a layperson than sorting or searching. Oct 19, 2010 at 18:01
• This is a really nice way to quickly get to the heart of the matter, thanks! Oct 19, 2010 at 18:17
• I have given the same example :) The reaction I have seen is people going into denial, almost getting angry with me: "what do you mean we don't know if multiplication is harder than addition? of course it is..are you playing games with me?" Jun 15, 2011 at 21:51
• I really like this answer, but it's not what I do! I work in a completely different field, namely dependent type theory. Should I explain "theory A" vs "theory B"?
– cody
Mar 24, 2015 at 14:53

I give people a concrete example. Specifically, I often motivate complexity theory with the same very illustrative (but simple) problem. I ask my audience how they would instruct a small child to discover whether his name is in an alphabetically sorted list of names (and tell them that it takes the child 3 seconds to compare any one name to another). It is often the case that the person/group will come up with the naive, linear approach. I force the conversation to turn to the logarithmic algorithm (I might use a different word than logarithm) either by asking the person for something better or by mentioning it myself. I show them how doubling the size of the list only adds three seconds of work for the child with this new approach. And I compare this directly with the linear version, which will now seem entirely silly.

Of course, I bring it back to earth. I tell them that child in question is generally a computer but that it could be a child or really anyone in general. That the questions we ask aren't really about computers but are more about the amount of space, time and information you need to solve problems. And I motivate complexity analysis by analogy to the two different methods for solving the same problem.

When I've got their attention - I bring out the heavy hitters. I ask them "can you prove that the logarithmic solution is the best you can ever hope to do or can you find something better?" and I ask them "are there problems that no process (algorithm) can hope to solve?" I've been surprised at how people try to tackle these questions when they don't have a TCS background.

• And for the record, I've had pretty good luck in terms of getting people close to me somewhat interested in the subject. Sep 20, 2010 at 2:02
• Before the effective demise of the telephone directory, this could have been turned into a snappy two-sentence response. Is there a canonical example of a random-access ordered list that everyone knows about? Sep 21, 2010 at 8:43
• Sure, András. The index of a book. Alternately, you could of course go for a new pack of cards before it has been shuffled, which would of course let you go on to consider the unordered case. Sep 21, 2010 at 15:52
• @Joe: I regularly meet people who haven't used textbooks with indices. Maybe if Harry Potter came with an index... Sep 21, 2010 at 16:02
• @András: I guess I've been eating in college too often! Surely nearly all school books have them. Sep 21, 2010 at 16:12

I like this post by Scott Aaronson, which explains complexity theory as quantitative theology. Here's an excerpt:

Computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They’re a great way to illustrate the point, they were probably essential for discovering the point, but they’re not the point.

The best definition of complexity theory I can think of is that it’s quantitative theology: the mathematical study of hypothetical superintelligent beings such as gods. Its concerns include:

• If a God or gods existed, how could they reveal themselves to mortals? (IP=PSPACE, or MIP=NEXP in the polytheistic case.)

• Which gods are mightier than which other gods? (PNP vs. PP, SZK vs. QMA, BQPNP vs. NPBQP, etc. etc.)

• Could a munificent God choose to bestow His omniscience on a mortal? (EXP vs. P/poly.)

• Can oracles be trusted? (Can oracles be trusted?)

And of course:

• Could mortals ever become godlike themselves? (P vs. NP, BQP vs. NP.)
• there can be only one God, Assuming multiple of Gods is logically inconsistent because multiple Gods will have different levels of attributes which contradicts the principle of a supreme God.(One God being mightier than another Gods is silly) Sep 20, 2010 at 3:41
• @Williams, my point is that the layperson will get confused with these analogies. Sep 20, 2010 at 4:04
• although I really shouldn't, I should point out that multiple gods are inconsistent only under the view that God-like properties form a total order. If they form a partial order, then it's perfectly fine to have multiple Gods. (sorry, Ryan) Sep 20, 2010 at 4:07
• @Suresh, Are you implying that there could be two Gods which we can't tell who is mightier? The binary relation here is total order. (sorry, Ryan) Sep 20, 2010 at 4:25

An example answer, which can definitely be improved:

Theoretical computer scientists study computation in mathematical terms. They can fix your computer about as well as mathematicians can calculate your taxes.

• Unfortunately, most people I know think that mathematicians would precisely be good at calculating taxes... Sep 20, 2010 at 1:55
• This reminds me of the famous quote by Dijkstra - "Computer science is no more about computers than astronomy is about telescopes." Sep 20, 2010 at 2:23
• Lez - Those people should be told about the Grothendiek Prime. Sep 20, 2010 at 2:41
• Here's another one, pulled from jondoda on Twitter: "Asking a computer scientist for tech support is like asking a botanist to mow your lawn." This one is getting warmer... Sep 20, 2010 at 17:31
• Ryan, the corollary being that both can easily accomplish the task but resent being asked? Sep 21, 2010 at 15:54

I think an excellent (non)-answer along these lines was given by Dijkstra (always a good source to turn to for crusty and absolutist pronouncements :)).

Computer Science is no more about computers than astronomy is about telescopes. - E. W. Dijkstra

I really like the introduction to the Partitioning problem as given by Brian Hayes given here.

He uses the problem of partitioning a set of children into teams of equal total ability (assuming you can quantify the ability of every child using a number), and also explains the greedy algorithm usually used by children to solve this problem.

It's a very simple problem to understand, it's easy to understand the algorithm, surprising that it is (most likely) very hard in general and embarrassing that we are still unable to prove the last bit.

• This is a really good one. Somehow I didn't notice it here before. Oct 21, 2010 at 19:37
• Loved the article! Nov 9, 2010 at 3:30

I usually answer with something along the lines of: I try to figure out what it is possible to do with a computer. It isn't completely accurate but it's pretty close, and usually people ask something like "What do you mean?" and I can reference something specific, like TSP. Although I rephrase traveling salesman as, say, the bar-hopping problem, the real-estate agent problem, the too-many-errands-not-enough-time problem, or whatever seems appropriate.

For example: "Well, let's say that you need to shop for shoes, groceries, and clothes, pick up a cake, get a haircut, and run some other miscellaneous errands before dinner. It would be great if you could put all that stuff into your GPS and it could tell you what order to do all your errands in to be done by 4 o'clock. But if the list of errands is long enough, it isn't even possible, right now, to figure out if you can get them done by 4 at all, much less what order you need to do them in, in any reasonable amount of time. I want to know if it's possible to solve that problem quickly with a computer."

• Great, I think that's the sort of response that would kick off an interesting conversation! Sep 25, 2010 at 15:12

What are the best ways to solve problems, and what problems are too hard to solve? There's a word in European languages -- including English! -- "informatics." The science of information. In the USA, we call this theoretical computer science, because of the strong computer industry here, but think about problem-solving without computers for a minute. Consider the human body. It solves problems in almost a miraculous fashion. Light comes into our eyes, and we can see things we recognize. Sound comes into our ears, and we hear words we understand. These are information problems we solve easily, thousands of times a day, that the best computers in the world still struggle with.

It took the process of evolution millions of years to solve those problems, using a strategy of trial-and-error, and killing off the unlucky. Imagine what we might accomplish if we took a more rational approach, and invested as much human creativity into this new science of problem-solving as we have invested into geometry, theology, or calculus. What I do is one small part of that investment.

In response to the layperson's question, "What do you do?" I have often answered, "I spend a lot of time staring into space, figuring out how to make science fiction real." Then I give a specific example of a project, explained in a couple sentences.

• Most people I know would think someone trying to make science fiction real was a physicist. How do you distinguish? Sep 20, 2010 at 10:58
• I would love it if an experimental scientist were to build something I have thought up. Why does there have to be a way to distinguish? But, to answer anyway: I think about microscopic computers, while physicists think about the properties of matter. Is there a difference? Depends what you care about, and what you emphasize. Sep 20, 2010 at 11:09
• This sounds to me like this explains what computer science is, but not what theoretical computer science is. Jul 27, 2012 at 9:02

Theoretical computer science is to computer science what mathematics used to be to physics.

• why "used to be" ? Oct 19, 2010 at 18:36
• I remember hearing something like: "CS to logic/combinatorics (TCS) is like physics to geometry." Oct 19, 2010 at 18:51
• Suresh, I think Andrej is claiming this: it used to be that the study of physics generated a large fraction of the problems studied by mathematicians, but this fraction has decreased over the years (now mathematics is much broader). I don't enough about the history of mathematics to say for sure that this is true, but what I do know is in line with it. Oct 19, 2010 at 20:29
• I don't think this analogy works, because laypeople also don't know about mathematics and physics. Jul 27, 2012 at 9:00

I usually give the following answer, albeit focused on complexity theory: "I study the boundaries, in term of space and time, for a problem to be solved. Problems include, finding the shortest path on a map or winning a chess game."

Usually I give the factoring problem as example; I first ask for the number that divide 15; usually people can answer 3, 5, and have fun wondering if 1 and 15 are correct answer. Then I give a huge number (more than 10 digits) and ask if they can tell me what are the dividers; and I explain that, even for computer scientist, this is a really hard question.

Then if I have time, I try to explain that the question is either to figure out how to solve this problem, or to prove that it will always take a lot of time( a notion that we precisely know how to define). And then a little word of cryptography, to explain why it is usedd, and a word about how many time it take team of scientist to break the key of number with hundreds of digit (I avoid to speak of bits because people seems to better know what a digit is)

The posed question is really a hard one since most people have no idea what computer scientists in general do. This is very different from other disciplines.

I like to use the following analogy: (T)CS is for computers what physics is for CD-Players (i.e. the laser). This actually works quite well because most people have an idea of what a physicist deals with, be it correct or not.

More specific examples include those things most people can relate to

• String Matching (slow naive approach vs daily experience of fast searching in Word, Browser, ...)
• Shortest Path Problem (as used in navigation systems)
• Scheduling (depending on the other's degree of nerdiness, refer to business processes or scheduling on CPU)

I would then explain that while PCS people would see to a fast implementation or good integration in complex systems, TCS people wonder about what is possible and proving things that provide safe, reusable knowledge/techniques for PCS to use.

You can also use people's frustration about computers ("It does not do what I want!"). You can point out that (T)CS deals with how to express things in a way computers can understand and process efficiently (referring to syntax, semantics, datastructures, algorithms).

When someone asks you a question, you can either answer it directly or you can give him a step by step procedure to follow and a proof that if the steps are followed accurately then the answer will be obtained within a reasonable amount of time. Given that the steps themselves are not too complicated and can be carried out quickly by an entity capable of existing in this universe, what kinds of questions exhibit such procedures? I think this is the subject of Theoretical Computer Science.

• The only issue is the talk of things existing within the universe. That kind of makes it physics rather than TCS. After all, the universe is a finite object, and a large portion of TCS deals with assymptotics. Sep 20, 2010 at 0:04
• Hmm, that's a good point. But do we really use asymptotics because we want to know how our algorithm will perform on input sizes that are bigger than the universe or do we use the big-Oh notation just to make our calculations roughly model independent? Sep 20, 2010 at 2:38
• Well, I certainly think things like deciding computability, etc., live on a more abstract level. Sep 20, 2010 at 16:59

My usual answer, which is not snappy but is guaranteed to stop conversation dead (bonus!) is "like quantum theory is the mathematical core of physics, TCS is the mathematical core of computer science".

• Actually, Theoretical Physics rather than quantum mechanics is the TCS of physics. There is a bunch of other physical theories besides quantum mechanics (classical general relativity being the most obvious example). Sep 20, 2010 at 0:05
• The goal isn't accuracy :) Sep 20, 2010 at 0:21
• But then one can further ask, "What is computer science?" Sep 20, 2010 at 2:34

We study the limits of computation. How quickly can you solve a certain computational problem? How much time is required to solve it, no matter what solution you try? Then I give them these examples (which are easy to explain to most laypeople -- and indeed many laypeople have direct experience with them -- demonstrate some properties of NP-complete problems, and actually have to do with saving lives).

Obviously people (including myself) might quip that I've ignored important other resources like space, randomness, or even quantumness. But when you only have 2 minutes to tell someone about a whole field, some things get left out.

If you want to give a whimsical look into the past, remind your audience that "computer" used to refer to a person whose profession was to compute things. (And if you want to violate some gender stereotypes that they may have, you can point out that these were frequently women, as well.)

You can then achieve a handful of things at once:

• make a convincing argument that "computer science" can be something beyond studying "computers";
• point out that people who are computing need some rules to accomplish their task (especially in a room full of "computers" doing specialist tasks — communication complexity and parallelization, anyone?), and this is just as true for machines;
• describe that "computer science" is about finding effective ways to solve problems involving "computing" in this sense;
• put the point across that just what exactly is doing the computing is not as important as the resources they need (such as time and scratch-space).

I always start by pointing them toward some creative, intentionally-irreverent video or article that explains a technical concept at an intuitive level. Here's a good example: Doodling in Math: Spirals, Fibonacci, and Being a Plant

Once they understand the concept (and hopefully have had a little fun with it), I try to generalize what they've learned to something about TCS. For instance, the above video could lead into a basic explanation of algorithms or computation as a recursive process -- "something that generates a complex structure out of a few, simple rules." TCS people, then, just study what types of rules produce what types of structure!

From there, it's generally easy enough to go from general TCS to the domain-specific thing you do. :)

Following the suggestion given by Ross Snider, of starting with a specific example, one can also directly explain the P vs NP question. One can describe this question to a layperson as figuring out whether verifying a solution is provably easier than actually finding one, or is it true that whenever we can verify a solution, we can find it too?

Here's mine:

Computer science isn't just science, there's a lot of engineering in it, but the scientific part is about understanding computation. And a computation is a physical process that generates information in an orderly way. In theoretical computer science, we think we need relatively sophisticated mathematics to understand computation.

It leads nicely into talking about computation in biology, the role of logic in computer science, &c.

Maybe one could say that

a theoretical computer scientist studies really really hard problems related to computer science.

The scientist will not use a computer while being creative, but rather think a lot, scribble formulas and quirky drawings on paper and occasionally wander around. Thereby the immediate practicability is not the most important thing, it's more like an artist exploring and trying to make sense of the mysteries of this world.

Then one could mention things which rely on some elegant solutions by theoreticians, like the computer, the internet, search engines, secure banking, 3D movies, DNA sequencing, etc. But one should always stress that nobody knows the applications of today's research yet, some of it may first be seen in several decades.

From my experience, many people have an AHA-moment when they realize that computer science, and theory in special is so rich in interesting questions and problems to study. Many of which can be described on a high level! This is a list from Prof. Wikipedia (via SIGACT), pick your favorites: algorithms, data structures, computational complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness.

What does a theoretical computer scientist do, in terms that can be understood by people who are not computer scientists?

Pretty much the same as a VCR repair man. Both consider how to get the best performance out of machines which read and write information to extremely long bits of tape.

This may be a little more tongue in cheek than what you were after...

• It would certainly keep the conversation going! Sep 19, 2010 at 23:44
• Oh good. Can you tell me how to make the clock stop blinking 12:00? Sep 20, 2010 at 3:05
• Certainly, I charge the usual union rate. Sep 20, 2010 at 10:59
• I know this was a little tongue in cheek, but noticing the down votes, I will happily remove it if anyone has a serious problem with it. Sep 20, 2010 at 11:36
• No problem! I was worried that either some CS theorists or some VCR repairmen may have taken offense. Sep 21, 2010 at 0:09