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