On the Theory of Computing

by Anup Rao

 


I'm often asked the question "what do you do?". The question is typically posed by strangers and sometimes really means "who are you?". The short answers that are most appropriate in my case are "mathematician" and "computer scientist". The second label has the terrible effect that people think I care about the iPhone (I do), can help them buy a cheap computer (I can't) and/or am involved in making a lot of money in the tech industry (I wish). The first label is somewhat more accurate in terms of the type of work I do, and gives me a certain air of mystery, but has the problem that I may have to explain away the technicality that I actually work at computer science departments.

 

This article is an effort to give a reasonable answer to this question, one that I hope that anyone can understand, assuming the questioner really means "what do you do?" and not "who are you?".

 

The naming of "theory of computing" (from now "TOC"), my primary area of research, is unfortunate. It leads most people to think TOC has to do with speeding up the operation of computers, or with designing better software for computers. While some research in TOC does have an immediate impact on the way computers operate, a lot of the ideas are about a slew of different topics that at first sight may seem to have little to do with computers. Indeed, the uniting theme of TOC research is hard to describe, but it seems to have something to do with studying how information can be manipulated and measuring the costs associated with manipulating information. To understand the things we want to understand, we create mathematical models that describe the part of the world that we want to study. We then prove properties of these models, discovering facts that are true beyond any doubt about the mathematical models that we have designed.

 

To give an idea of the kinds of questions we think about, let us see some examples. We shall see several distinct examples with different themes. Here I will describe ideas in plain English, but keep in mind that everything that I'm going to talk about is backed up by very concrete mathematical models and proofs.

 


    The Power of Interaction

 

Suppose a blind man finds himself at a store with the goal of buying two differently colored sheets of paper. The blind man doesn't trust the salesman at the store to be honest about the color of the paper. Is there a way that he can use the salesman to convince himself that the sheets of paper he is buying are in fact different in color, even though he cannot tell the difference himself?

 

There is a simple solution to this task: the blind customer can first ask the salesman to identify what the colors of the sheets of paper are. Then he takes the sheets behind his back and shuffles them, keeping track of where each paper is before asking the salesman to again identify the colors of the sheets. If the two sheets are indistinguishable, the salesman cannot keep track of what colors he assigned to which sheets and the best he can do is get lucky to pass the test with a chance of 50%. If the customer repeats the test many times, he can make sure that the chance that the salesman has of tricking him is so small as to be insignificant. On the other hand, if the sheets are in fact of a different color, the salesman will never make a mistake. In this way, the blind man can make sure that the sheets he is buying can be distinguished by the salesman.

 

The idea that a "computationally stronger" person can convince a "computationally weaker" person, of something that the weaker person cannot figure out for himself is a very powerful and fundamental discovery in TOC. In the example above, computational strength was measured in terms of the ability to see, but the same ideas can be applied in the case that the computationally stronger party has a more powerful computer, or knows some secret that the weaker party does not know. Among other things, these ideas have led to the discovery of the beautiful and counter-intuitive concept of Zero Knowledge Proofs. These are ways for two people A and B to talk to each other so that A is convinced that B knows a secret, yet A learns no information about that secret! Imagine that we'd like a system for customers at a bank to have a certain password that gives them access to their account. If a customer walks up to the counter, he doesn't want to reveal his password to the clerk behind the counter, but he does want to convince the clerk that he knows the password. Zero Knowledge Proofs give a way for the two parties to talk to each other so that at the end of the conversation, the clerk can be confident that the customer knows the password, yet the customer can be confident that the clerk does not know anything about his password!

 


    Using Randomness to gain an Advantage

 

Let's imagine that we are stuck in a maze with 1000 identically furnished rooms and we don't know how the rooms are connected to each other before hand. What's the best way to find the exit of the maze?


The first thing one might think of is to map the maze: start walking the maze room by room, remembering where we've been and learning more and more about how the rooms are connected to each other. That idea may work when the number of rooms is small, but with a 1000 rooms, keeping track of where things are seems hopelessly complicated. If we knew that the rooms were all on one floor, then we could walk along one of the walls of the maze, walking through doors so that the wall is always to our left. That would guarantee that we'd visit every room on the floor without having to remember where we've been before. This idea doesn't work if all the rooms of the maze are not on the same floor, since we may come to a situation where it is not clear which of the exits of the room we should take next without once again making a big map. Surprisingly, it can be shown that if we simply walk the maze at random, picking the exits from each subsequent room randomly, we are extremely likely to visit every room in the maze in a relatively short amount of time, no matter what the shape of the maze! In other words, the chance that we don't find the exit of the maze in this random path is extremely small, so small that finding the exit is essentially a certainty. This is a very nice solution, because once we know that it works, executing it takes almost no effort.


Next suppose we are organizing a dinner party with seating at two different tables. The guests all have relationships with each other, each pair of guests are either friends or strangers. What we'd like to do is seat the guests at the two tables in such a way that the number of pairs of guests who are strangers and sit at different tables is maximized. How can we figure out the best arrangement of guests? This is a surprisingly difficult task. We still don't have any idea of how to do this that is any better than simply trying every single arrangement until we find the best one! On the other hand, it's quite easy to prove that if we assign each guest to a table at random by flipping a coin, we can expect to get an arrangement that is at least half as good as the best arrangement; the number of pairs of strangers who end up at different tables will typically be half as high as it can possibly be. So again, this simple random process gives something quite good.


In fact, these examples point to something that is more of a rule than an exception. The use of randomness is widespread, and not just in our limited context. For example, random mutations to genetic code are the key mechanism through which species adapt to unpredictable challenges and evolve into better versions. Our best physics models indicate that our universe also evolves randomly, the current state of the world does not determine the state of the world in the future.


Since doing things at random is so often the best way to deal with many tasks, TOC has invested a lot of effort in the past few decades to understand exactly why doing things at random is such a good idea, and whether or not this use of randomness is really necessary. For example, in the dinner party above, we can achieve the same kind of result with a process that does not involve randomness: we seat the guests at the two tables as they walk in. As each guest walks in, we look at which table has more strangers for this guest, and seat the guest at the other table. This process also guarantees that we obtain an arrangement that's half as good as the best one, though it's a bit more tiresome to implement than the idea that used randomness, since we could have had each guest flip their own coins and do the random solution in parallel. So here the randomness was not really necessary; one could achieve the same result using a slightly more inefficient non-random process.


An example of a basic question that we'd like to answer is: is it true that every task that can be handled efficiently with a random process, must have a solution of comparable efficiency that does not involve doing things randomly? This vague question can be formulated (via the powerful mathematical models developed in TOC) into a very concrete mathematical problem. The answer to this question is still unknown and is one of my own major research interests.

 


    Reductions between Tasks and Classes of Tasks

 

Now it may seem that the tasks that we have discussed so far (navigating mazes, figuring out seating arrangements) are just curiosities; ideas that we develop to tackle a particular kind of task may seem to have nothing to do with ideas needed to complete other kinds of tasks. However, it turns out that there are actually many connections (called reductions) between different types of tasks. This is a very basic concept that we are all already familiar with. Consider the task of multiplying two large numbers by hand. We all know how to do this: we write the numbers down and start working on the digits one by one, multiplying single digits and adding them. This is an example of a reduction. in this case we have learnt how to reduce the task of multiplying two large numbers to the task of multiplying and adding single digit numbers. As long as we know how to multiply and add single digits, we can accomplish the harder task of multiplying many digit numbers.


There are some tasks which are extremely powerful, in the sense that a very large class of other tasks can be reduced to them. A class of tasks for our purposes is a collection of tasks that are all comparable in difficulty. The simplest example of a class of tasks might be the class of tasks that can be handled efficiently. Another meaningful class is the class of tasks whose solutions can be checked/verified efficiently. Consider the task of figuring out whether a set of objects can fit into a suitcase or not. Clearly, if someone shows us how to pack the objects into the suitcase, we can easily verify that the objects fit into the suitcase. So this task is in the second class above. However, we know of no efficient way to decide whether a set of objects will fit into a suitcase or not, so this task may or may not be in the first class.

An amazing discovery in TOC is that any task whose solutions can be checked efficiently, can be reduced to finding whether or not objects can be packed into a suitcase! In TOC jargon, we say that packing a suitcase is complete for the class of tasks whose solutions can be checked efficiently. It turns out that finding the shortest route that visits a collection of cities is also such a complete task, as is the task of finding the best seating arrangement for the guests at the two tables in our party from above. For each of these tasks, we know of essentially no way of accomplishing them that is any better than simply trying all possibilities (i.e., trying all seating arrangements, all possible ways to place the objects in our suitcase or all possible routes for the tour)! Of course, people all over the world regularly pack suitcases, plan tours and arrange dinner parties where their guests have great conversations. But the point is that we have discovered no general solution to these problem that works no matter what the sizes of the objects we want to pack are or what the distances between the cities in our tour are or what the relationships between the guests are. This is in strong contrast to our method of multiplying numbers, which is guaranteed to work no matter what the numbers are.

The fact that there are reductions between these tasks means that anyone who figures out how to plan a tour efficiently will be able to use that knowledge to get a method to help her pack her travel suitcase efficiently and a method to arrange seating for her farewell dinner party, all in one fell swoop! On the other hand, if someone manages to use TOC mathematical models to prove that there is no way to pack a suitcase efficiently, this would mean that there is no way to plan a tour or find the best seating arrangement efficiently either!

Understanding whether or not these types of tasks can be efficiently handled is perhaps the central question in TOC today (one that carries a million dollars in prize money: http://www.claymath.org/millennium/), exactly because of the relevance to a whole variety of other tasks.



    Conclusion


A question that I haven't yet addressed is: what's the point of thinking about these things? I'm tempted to respond by quoting the late great physicist Richard Feynman: "Physics is like sex. Sure, it may give some practical applications, but that's not why we do it." This sentiment hits very close to the mark for most scientists that I know. The biggest motivators for most people who work in my area are curiosity and an appreciation for the beauty of the questions and theories that we have developed to address the issues that we study. On the other hand, there have been many major practical applications that have origins in TOC. One example is in the area of cryptography. This is the study of methods to transmit and keep secrets. Every time we use the Internet to transmit sensitive information such as credit card numbers, ideas that originated in TOC come in to play to ensure that someone who intercepts the transmissions from your computer will not be able to decipher the sensitive information. Another example is the theory of error correcting codes, which are used to encode information in such a way that even if a large part of the encoded information is changed, the original information can be recovered. These ideas show up today in the design of compact discs and DVD's, and are the reason why DVD players can play DVD's even if they have scratches on them. Other advances in TOC have played roles in speeding up the operation of the internet and in creating computer models for phenomena in physics.

While I feel that the TOC examples we have seen in this article are illustrative, they are by no means comprehensive. There are many different questions and whole areas of exciting research that are quite different in flavor from what we have seen here. Still, I hope that the reader will have got a sense for how common place the types of issues we study are, and how simple things that we do in our everyday lives can pose questions to us that we still don't know the answers to.


    Acknowledgements

The example of the blind man acquiring wall paper is taken from a website of Oded Goldreich's. Thanks to Daniel Lieber for useful comments. Thanks to the many people who suggested that I write an article of this type.


    Bio

Anup Rao recently completed his Ph.D. in computer science at the University of Texas at Austin. He is now a postdoctoral researcher at the Institute for Advanced Study, Princeton, New Jersey, USA.