<p>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.</p>

<p>Of course, I bring it back to earth. I tell them that child in question is generally a computer but that it <em>could</em> 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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-20T02:02:03.330Z
And for the record, I've had pretty good luck in terms of getting people close to me somewhat interested in the subject.
Ross Snider
CC BY-SA 2.5
2010-09-21T08:43:10.450Z
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?
András Salamon
CC BY-SA 2.5
2010-09-21T15:52:16.760Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-21T16:02:08.090Z
@Joe: I regularly meet people who haven't used textbooks with indices.  Maybe if Harry Potter came with an index...
András Salamon
CC BY-SA 2.5
2010-09-21T16:12:32.823Z
@András: I guess I've been eating in college too often! Surely nearly all school books have them.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-04T01:06:03.607Z
@Andras, my first thought for this kind of random access would be a dictionnary
Arthur MILCHIOR
CC BY-SA 2.5
2010-10-04T01:14:22.413Z
@Arthur: yes, that was my second thought after the phone book (and before a book index), but then I realised that I hadn't used mine for over a year, but the browser keywords to search three different online dictionaries get used daily...
András Salamon
CC BY-SA 2.5
2010-09-20T02:01:24.407Z
2010-09-20T23:48:22.250Z
2010-09-20T23:48:22.250Z
Ross Snider
<p>I like <a href="http://scottaaronson.com/blog/?p=56" rel="noreferrer">this post by Scott Aaronson</a>, which explains complexity theory as quantitative theology. Here's an excerpt:</p>
<blockquote>
<p>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.</p>
<p>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:</p>
<ul>
<li><p>If a God or gods existed, how could they reveal themselves to mortals? (IP=PSPACE, or MIP=NEXP in the polytheistic case.)</p>
</li>
<li><p>Which gods are mightier than which other gods? (P<sup>NP</sup> vs. PP, SZK vs. QMA, BQP<sup>NP</sup> vs. NP<sup>BQP</sup>, etc. etc.)</p>
</li>
<li><p>Could a munificent God choose to bestow His omniscience on a mortal? (EXP vs. P/poly.)</p>
</li>
<li><p>Can oracles be trusted? (Can oracles be trusted?)</p>
</li>
</ul>
<p>And of course:</p>
<ul>
<li>Could mortals ever become godlike themselves? (P vs. NP, BQP vs. NP.)</li>
</ul>
</blockquote>

CC BY-SA 2.5
2010-09-20T03:41:06.530Z
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)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-20T04:04:55.480Z
@Williams, my point is that the layperson will get confused with these _analogies_.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-20T04:07:53.263Z
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)
Suresh Venkat
CC BY-SA 2.5
2010-09-20T04:25:33.663Z
@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)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-20T02:46:08.910Z
2010-09-20T02:46:08.910Z
2020-06-17T09:38:08.363Z
Robin Kothari
<p>An example answer, which can definitely be improved:</p>

<blockquote>
  <p>Theoretical computer scientists study computation in mathematical terms.  They can fix your computer about as well as mathematicians can calculate your taxes.</p>
</blockquote>

CC BY-SA 3.0
2013-04-20T11:30:13.960Z
Sorry for the stupid question but why can't a mathematicians calculate my taxes? They're good at doing calculations, right?
Celmaun
CC BY-SA 2.5
2010-09-20T01:55:29.993Z
Unfortunately, most people I know think that mathematicians would precisely be good at calculating taxes...
Lev Reyzin
CC BY-SA 2.5
2010-09-20T02:23:08.273Z
This reminds me of the famous quote by Dijkstra - "Computer science is no more about computers than astronomy is about telescopes."
Vinayak Pathak
CC BY-SA 2.5
2010-09-20T02:41:38.460Z
Lez - Those people should be told about the Grothendiek Prime.
Vinayak Pathak
CC BY-SA 2.5
2010-09-20T03:46:36.860Z
Another try: "They can fix your computer about as well as a landscape painter can actually *build a landscape*, with bulldozers, dirt-hauling dump trucks, sowing grass and flower seeds, etc." Not a perfect analogy, since in TCS the landscapes are often painted without the crutch of a real landscape as a reference point.
Ryan Williams
CC BY-SA 2.5
2010-09-20T12:15:16.363Z
@Ryan: do you think working without "real" reference points is a weakness?  It always strikes me as unfair when a physicist looks at a problem, says "that's just like X" where X is some phenomenon we have observed in the universe, and then proceeds to give a hacky solution that works quite well, based on the analogy.  Yet for most discrete phenomena this is a bad approach, because there are few well-understood natural discrete processes, and because combinatorial behaviour tends to depend on fine details.
András Salamon
CC BY-SA 2.5
2010-09-20T16:45:58.457Z
No, I thought the "weakness" was in the analogy itself. I called a real landscape a "crutch", didn't I? :)
Ryan Williams
CC BY-SA 2.5
2010-09-20T17:31:40.717Z
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...
Ryan Williams
CC BY-SA 2.5
2010-09-21T08:44:18.547Z
@Ryan: With the rise of CompBio this one is likely to prove useful -- thanks!
András Salamon
CC BY-SA 2.5
2010-09-21T15:54:56.300Z
Ryan, the corollary being that both can easily accomplish the task but resent being asked?
Joe Fitzsimons
CC BY-SA 2.5
2010-09-20T00:36:06.220Z
2010-09-20T00:36:06.220Z
András Salamon
<p>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 :)).</p>

<blockquote>
  <p>Computer Science is no more about
  computers than astronomy is about
  telescopes.
  - E. W. Dijkstra</p>
</blockquote>

CC BY-SA 2.5
2010-09-20T04:09:15.990Z
2010-09-20T04:09:15.990Z
Suresh Venkat
<p>I really like the introduction to the Partitioning problem as given by Brian Hayes given <a href="http://www.americanscientist.org/issues/pub/the-easiest-hard-problem/1">here</a>.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-09T03:30:14.640Z
Loved the article!
arnab
CC BY-SA 2.5
2010-10-21T19:37:01.930Z
This is a really good one. Somehow I didn't notice it here before.
Ryan Williams
CC BY-SA 2.5
2010-09-20T23:30:31.793Z
2010-09-20T23:30:31.793Z
Alex ten Brink
<p>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.</p>

<p>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 <em>can</em> get them done by 4 <em>at all</em>, 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."</p>

CC BY-SA 2.5
2010-09-25T15:12:19.670Z
Great, I think that's the sort of response that would kick off an interesting conversation!
András Salamon
CC BY-SA 2.5
2010-09-24T21:43:38.820Z
2010-09-24T21:43:38.820Z
philosodad
<p>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 <i>recognize</i>.  Sound comes into our ears, and we hear words we <i>understand</i>.  These are information problems we solve easily, thousands of times a day, that the best computers in the world still struggle with.</p>

<p>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.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2012-07-27T09:02:11.367Z
This sounds to me like this explains what computer science is, but not what theoretical computer science is.
Zsbán Ambrus
CC BY-SA 2.5
2010-09-20T10:58:05.797Z
Most people I know would think someone trying to make science fiction real was a physicist.  How do you distinguish?
András Salamon
CC BY-SA 2.5
2010-09-20T11:09:12.413Z
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.
Aaron Sterling
CC BY-SA 2.5
2010-09-20T01:38:15.447Z
2010-09-20T01:38:15.447Z
Aaron Sterling
<p>Theoretical computer science is to computer science what mathematics used to be to physics.</p>

CC BY-SA 3.0
2012-07-27T09:00:08.640Z
I don't think this analogy works, because laypeople also don't know about mathematics and physics.
Zsbán Ambrus
CC BY-SA 2.5
2010-10-19T18:36:23.247Z
why "used to be" ?
Suresh Venkat
CC BY-SA 2.5
2010-10-19T18:51:53.493Z
I remember hearing something like: "CS to logic/combinatorics (TCS) is like physics to geometry."
Kaveh
CC BY-SA 2.5
2010-10-19T20:29:35.797Z
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.
Ryan Williams
CC BY-SA 2.5
2010-10-19T18:20:22.510Z
2010-10-19T18:20:22.510Z
Andrej Bauer
<p>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.</p>

<p>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)</p>

CC BY-SA 2.5
2010-10-04T01:35:35.510Z
2010-10-04T01:35:35.510Z
Arthur MILCHIOR
<p>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.</p>

<p>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.</p>

<p>More specific examples include those things most people can relate to</p>

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

<p>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.</p>

<p>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).</p>

CC BY-SA 2.5
2010-10-04T07:36:34.863Z
2010-10-04T07:36:34.863Z
Raphael
<p>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."</p>

CC BY-SA 2.5
2010-09-20T01:11:01.790Z
2010-09-20T01:11:01.790Z
Michaël Cadilhac
<p>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". </p>

CC BY-SA 2.5
2010-09-20T00:05:48.743Z
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).
Joe Fitzsimons
CC BY-SA 2.5
2010-09-20T00:21:10.983Z
The goal isn't accuracy :)
Suresh Venkat
CC BY-SA 2.5
2010-09-20T02:34:33.067Z
But then one can further ask, "What is computer science?"
Vinayak Pathak
CC BY-SA 2.5
2010-09-20T00:00:24.040Z
2010-09-20T00:00:24.040Z
Suresh Venkat
<p>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: <a href="http://www.youtube.com/watch?v=ahXIMUkSXX0" rel="nofollow">Doodling in Math: Spirals, Fibonacci, and Being a Plant</a></p>

<p>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!</p>

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

CC BY-SA 3.0
2012-07-21T17:26:53.667Z
2012-07-21T17:26:53.667Z
Daniel Apon
<p>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 <a href="https://cstheory.stackexchange.com/questions/446/everyday-encounters-with-np-complete-problems/495#495">these examples</a> (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).</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-20T22:24:30.503Z
2010-09-20T22:24:30.503Z
2017-04-13T12:32:28.077Z
Joshua Grochow
<p>If you want to give a whimsical look into the past, remind your audience that "computer" used to refer to a <em>person whose profession was to compute things</em>. (And if you want to violate some gender stereotypes that they may have, you can point out that these were frequently women, as well.)</p>

<p>You can then achieve a handful of things at once:</p>

<ul>
<li>make a convincing argument that "computer science" can be something beyond studying "computers";</li>
<li>point out that people who are computing need <em>some</em> rules to accomplish their task (especially in a room full of "computers" doing specialist tasks &mdash; communication complexity and parallelization, anyone?), and this is just as true for machines;</li>
<li>describe that "computer science" is about finding effective ways to solve problems involving "computing" in this sense;</li>
<li>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).</li>
</ul>

CC BY-SA 2.5
2010-10-04T08:19:01.380Z
2010-10-04T08:19:01.380Z
Niel de Beaudrap
<p>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.</p>

CC BY-SA 2.5
2010-09-20T00:04:00.933Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-20T02:38:22.807Z
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?
Vinayak Pathak
CC BY-SA 2.5
2010-09-20T16:59:36.383Z
Well, I certainly think things like deciding computability, etc., live on a more abstract level.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-19T23:59:14.047Z
2010-09-19T23:59:14.047Z
Vinayak Pathak
<p>Here's mine:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>It leads nicely into talking about computation in biology, the role of logic in computer science, &amp;c.</p>

CC BY-SA 2.5
2010-09-20T11:08:31.650Z
2010-09-20T11:08:31.650Z
Charles Stewart
<p>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? </p>

CC BY-SA 2.5
2010-09-20T04:46:42.467Z
2010-09-20T04:46:42.467Z
Vinayak Pathak
<p>Maybe one could say that </p>

<blockquote>
  <p>a theoretical computer scientist
  studies really really hard problems
  related to computer science.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-16T12:43:40.253Z
2010-10-16T12:43:40.253Z
Michael
<blockquote>
  <p>What does a theoretical computer scientist do, in terms that can be understood by people who are not computer scientists?</p>
</blockquote>

<p>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.</p>

<p>This may be a little more tongue in cheek than what you were after...</p>

CC BY-SA 3.0
2013-09-26T10:26:18.120Z
What is a VCR?  ;)
Jan Johannsen
CC BY-SA 2.5
2010-09-19T23:44:39.447Z
It would certainly keep the conversation going!
András Salamon
CC BY-SA 2.5
2010-09-20T03:05:58.260Z
Oh good. Can you tell me how to make the clock stop blinking 12:00?
Jeffε
CC BY-SA 2.5
2010-09-20T10:59:34.203Z
Certainly, I charge the usual union rate.
András Salamon
CC BY-SA 2.5
2010-09-20T11:36:28.080Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-20T11:43:08.023Z
It got +1 from me...
András Salamon
CC BY-SA 2.5
2010-09-20T13:29:51.317Z
JeffE: Yes: Set the time!
Joe Fitzsimons
CC BY-SA 2.5
2010-09-20T19:52:14.177Z
I'll explain my -1: the answer makes for a good joke, but as a practical explanation, it would give people an impression that TCS is the opposite of what it really is.  A VCR repair man fixes VCRs, so a theoretical computer scientist must fix computers?
Lev Reyzin
CC BY-SA 2.5
2010-09-20T20:45:01.300Z
Ok, well I just wanted to check the answer hadn't actually annoyed anyone.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-20T22:40:02.187Z
Not annoyed - just cast an honest vote...
Lev Reyzin
CC BY-SA 2.5
2010-09-21T00:09:15.037Z
No problem! I was worried that either some CS theorists or some VCR repairmen may have taken offense.
Joe Fitzsimons
CC BY-SA 2.5
2010-09-19T23:38:24.490Z
2010-09-19T23:38:24.490Z
Joe Fitzsimons
<p>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?</p>

<p>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.  </p>

CC BY-SA 3.0
2011-06-15T21:51:44.717Z
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?"
Sasho Nikolov
CC BY-SA 3.0
2015-03-24T14:53:36.590Z
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
CC BY-SA 2.5
2010-10-19T18:01:29.593Z
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.
Lev Reyzin
CC BY-SA 2.5
2010-10-19T18:17:49.567Z
This is a really nice way to quickly get to the heart of the matter, thanks!
András Salamon
CC BY-SA 2.5
2010-10-19T17:52:27.647Z
2010-10-19T17:52:27.647Z
Aubrey da Cunha
<p>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.</p>

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

<p>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.</p>

<p>This question is inspired by the MO question <a href="https://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics">https://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics</a> although the intent is different.</p>

<big-list><soft-question>
Dinner-table description of theoretical computer science?
András Salamon
# Dinner-table description of theoretical computer science?

(Asked by: username_0 on 2010-09-19)

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.

**Tags:** big-list, soft-question


---

## 21 answers

### Answer by username_27 on 2010-10-19. Score: 36 | Accepted answer

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.

> **Comments:**
> **username_8**: 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.  
> **username_0**: This is a really nice way to quickly get to the heart of the matter, thanks!  
> **username_28**: 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?"  
> **username_29**: 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"?  

---

### Answer by username_1 on 2010-09-20. Score: 39

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.

> **Comments:**
> **username_1**: And for the record, I've had pretty good luck in terms of getting people close to me somewhat interested in the subject.  
> **username_0**: 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?  
> **username_2**: 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.  
> **username_0**: @Joe: I regularly meet people who haven't used textbooks with indices.  Maybe if Harry Potter came with an index...  
> **username_2**: @András: I guess I've been eating in college too often! Surely nearly all school books have them.  
> **username_3**: @Andras, my first thought for this kind of random access would be a dictionnary  
> **username_0**: @Arthur: yes, that was my second thought after the phone book (and before a book index), but then I realised that I hadn't used mine for over a year, but the browser keywords to search three different online dictionaries get used daily...  

---

### Answer by username_4 on 2010-09-20. Score: 21

I like [this post by Scott Aaronson](http://scottaaronson.com/blog/?p=56), 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.)

> **Comments:**
> **username_5**: 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)  
> **username_5**: @Williams, my point is that the layperson will get confused with these _analogies_.  
> **username_6**: 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)  
> **username_5**: @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)  

---

### Answer by username_0 on 2010-09-20. Score: 18

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.

> **Comments:**
> **username_8**: Unfortunately, most people I know think that mathematicians would precisely be good at calculating taxes...  
> **username_9**: This reminds me of the famous quote by Dijkstra - "Computer science is no more about computers than astronomy is about telescopes."  
> **username_9**: Lez - Those people should be told about the Grothendiek Prime.  
> **username_10**: Another try: "They can fix your computer about as well as a landscape painter can actually *build a landscape*, with bulldozers, dirt-hauling dump trucks, sowing grass and flower seeds, etc." Not a perfect analogy, since in TCS the landscapes are often painted without the crutch of a real landscape as a reference point.  
> **username_0**: @Ryan: do you think working without "real" reference points is a weakness?  It always strikes me as unfair when a physicist looks at a problem, says "that's just like X" where X is some phenomenon we have observed in the universe, and then proceeds to give a hacky solution that works quite well, based on the analogy.  Yet for most discrete phenomena this is a bad approach, because there are few well-understood natural discrete processes, and because combinatorial behaviour tends to depend on fine details.  
> **username_10**: No, I thought the "weakness" was in the analogy itself. I called a real landscape a "crutch", didn't I? :)  
> **username_10**: 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...  
> **username_0**: @Ryan: With the rise of CompBio this one is likely to prove useful -- thanks!  
> **username_2**: Ryan, the corollary being that both can easily accomplish the task but resent being asked?  
> **username_7**: Sorry for the stupid question but why can't a mathematicians calculate my taxes? They're good at doing calculations, right?  

---

### Answer by username_6 on 2010-09-20. Score: 17

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


---

### Answer by username_11 on 2010-09-20. Score: 11

I really like the introduction to the Partitioning problem as given by Brian Hayes given [here](http://www.americanscientist.org/issues/pub/the-easiest-hard-problem/1).

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.

> **Comments:**
> **username_10**: This is a really good one. Somehow I didn't notice it here before.  
> **username_12**: Loved the article!  

---

### Answer by username_13 on 2010-09-24. Score: 8

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."

> **Comments:**
> **username_0**: Great, I think that's the sort of response that would kick off an interesting conversation!  

---

### Answer by username_14 on 2010-09-20. Score: 7

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.

> **Comments:**
> **username_0**: Most people I know would think someone trying to make science fiction real was a physicist.  How do you distinguish?  
> **username_14**: 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.  
> **username_15**: This sounds to me like this explains what computer science is, but not what theoretical computer science is.  

---

### Answer by username_16 on 2010-10-19. Score: 6

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

> **Comments:**
> **username_6**: why "used to be" ?  
> **username_17**: I remember hearing something like: "CS to logic/combinatorics (TCS) is like physics to geometry."  
> **username_10**: 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.  
> **username_15**: I don't think this analogy works, because laypeople also don't know about mathematics and physics.  

---

### Answer by username_3 on 2010-10-04. Score: 5

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)


---

### Answer by username_18 on 2010-10-04. Score: 5

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


---

### Answer by username_19 on 2010-09-20. Score: 5

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."


---

### Answer by username_6 on 2010-09-20. Score: 4

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".

> **Comments:**
> **username_2**: 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).  
> **username_6**: The goal isn't accuracy :)  
> **username_9**: But then one can further ask, "What is computer science?"  

---

### Answer by username_20 on 2012-07-21. Score: 4

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](http://www.youtube.com/watch?v=ahXIMUkSXX0)

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


---

### Answer by username_21 on 2010-09-20. Score: 4

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](https://cstheory.stackexchange.com/questions/446/everyday-encounters-with-np-complete-problems/495#495) (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.


---

### Answer by username_22 on 2010-10-04. Score: 4

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


---

### Answer by username_9 on 2010-09-19. Score: 4

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.

> **Comments:**
> **username_2**: 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.  
> **username_9**: 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?  
> **username_2**: Well, I certainly think things like deciding computability, etc., live on a more abstract level.  

---

### Answer by username_23 on 2010-09-20. Score: 2

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.


---

### Answer by username_9 on 2010-09-20. Score: 2

Following the suggestion given by username_1, 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?


---

### Answer by username_24 on 2010-10-16. Score: 2

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.


---

### Answer by username_2 on 2010-09-19. Score: 0

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

> **Comments:**
> **username_0**: It would certainly keep the conversation going!  
> **username_26**: Oh good. Can you tell me how to make the clock stop blinking 12:00?  
> **username_0**: Certainly, I charge the usual union rate.  
> **username_2**: 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.  
> **username_0**: It got +1 from me...  
> **username_2**: JeffE: Yes: Set the time!  
> **username_8**: I'll explain my -1: the answer makes for a good joke, but as a practical explanation, it would give people an impression that TCS is the opposite of what it really is.  A VCR repair man fixes VCRs, so a theoretical computer scientist must fix computers?  
> **username_2**: Ok, well I just wanted to check the answer hadn't actually annoyed anyone.  
> **username_8**: Not annoyed - just cast an honest vote...  
> **username_2**: No problem! I was worried that either some CS theorists or some VCR repairmen may have taken offense.  
> **username_25**: What is a VCR?  ;)  

---

