Move the Cheese

Martin Strauss and Anna Gilbert and Atri Rudra are the organizers of the just-held Coding, Complexity, and Sparsity Workshop. The theme of sparsity is working with objects that in their “vanilla” representation have many parts that are zero, redundant, or otherwise trivial. For instance, you might have an matrix in which is huge but every row and/or column has just a few non-zero entries. The game is to find alternative succinct representations and clever algorithms to exploit them, also tailoring the objects to major toolkits such as for linear or semidefinite programming, regression, finite-element analysis, feature extraction, and equation solving.

Today Ken and I want to thank them for having us attend this fun meeting.

The workshop was held this past Monday through Wednesday in Ann Arbor at the University of Michigan. The speakers, with perhaps one exception, were great, knowledgeable, and gave great talks. Okay the exception is me—I cannot comment on my talk.

There was another special talk, which was terrific; and one I can comment on without reservation. Ken helped fill in a gap in the program, since someone had to cancel. Even though his talk started at almost five o’clock, after a long day of talks, it was clearly one of the best. He spoke on his work on cheating in chess. There is something engaging about his area. It combines a game that many of us love, with human drama—cheating—and also includes lots of computing and math issues. See our recent discussion of chess cheating. Ken thanks the organizers for the opportunity.

Themes

In the famous motivational book by Spencer Johnson, Who Moved My Cheese?, the main topic is about change in the workplace. Well, we who do research face lots of change too.

The book is summarized as follows:

• Change Happens
• They Keep Moving The Cheese
• Anticipate Change
• Get Ready For The Cheese To Move
• Monitor Change
• Smell The Cheese Often So You Know When It Is Getting Old
• Adapt To Change Quickly
• The Quicker You Let Go Of Old Cheese, The Sooner You Can Enjoy New Cheese
• Change
• Move With The Cheese
• Enjoy Change!
• Savor The Adventure And Enjoy The Taste Of New Cheese!
• Be Ready To Change Quickly And Enjoy It Again
• They Keep Moving The Cheese.

Okay how does this connection to the workshop, and to research? Well the area you do research in is like the cheese. What I noticed during the workshop was that the cheese—I mean the research topics—were often old topics that had been moved. I think it is fine to keep working on the same problem, but often the research that is exciting is the result of moving the cheese.

Let me give three examples of this. Let me also in advance say that just about everyone could be used as examples of this idea: change the topic, or move the cheese. So please do not be upset if I do not use your favorite area as an example, and Ken and I hope to discuss others in the future.

Three Examples

Sparse FFT’s: The Fast Fourier Transform has long been of great importance in theory and in practice. It of course runs in near linear time: time where is the number of points. But a clever way to move this cheese is not to work on the still open problem: is there a way to compute the FFT in linear time? Rather move the cheese and make the question: Is there some way to do the FFT with less samples than ? It turns out that in many practical cases, the running time is much less important than the number of samples. The beautiful result is that provided the signal is sparse it possible to almost get the FFT in time linear in . This is a huge improvement in many real-world situations.

Linear Systems: The solving of huge linear systems is becoming more and more important. One of the neat insights is that if these systems arise from a relaxation problem, then solving them to high precision may be unneeded. If the answers are going to be rounded, say, to the nearest integer, then why compute them to high precision? This moving of the cheese seems to be a very cool idea. And it promises to radically change the way many linear systems are approached.

Sylvester’s Problem: James Sylvester posed a problem that at first may seem just a curiosity for Victorian-era puzzle books: Given any points in the plane, not all collinear, show there must be a straight line that is incident on only two of the points. You may enjoy trying to prove this by assuming all lines hit three or more points and considering a point with minimum distance to a non-incident line. The “movement” is to consider points in higher-dimensional space, and/or planes or other affine linear subspaces instead of lines—and/or also to change to complex or projective or other kinds of space or relax exact collinearity to approximate. Then this kind of problem gives new twists on issues about matrix rank and combinatorial designs and even directly relates to the complexity of arithmetic circuits. See a couple recent papers by presenter Shubhangi Saraf.

Where to begin learning a field, given that it will move on you? The workshop has the great idea of giving tutorials in some selected areas at the beginning. Here are summaries of the three tutorials this year, with my comments after the speakers’ abstracts. The first two in fact were given by current graduate students.

The Tutorials

Mary Wootters: High dimensional probability in theoretical computer science

Recently, techniques from probability in Banach spaces and geometric functional analysis have found applications in compressed sensing, coding theory, and other areas of theoretical computer science. In this tutorial, I will go over some useful tricks and techniques, with examples.

At the start she said that she would “lie” during the tutorial—if this were a logic seminar we would have asked if she were lying about that statement. Her goal is to help improve the union bound. Recall this is the simple, but amazingly useful observation: The probability of the conjunction of events is bounded by

One method is called symmetrization. She showed how to replace a sum

by

for suitably-chosen and get about the same expectation. This can vastly simplify a calculation, which she exploited in an example from coding theory.

She then switched to union bounds over geometric objects. These have extra structure which is possible to exploit. One especially is their covering number. For a spatial set , this is defined as the number of -radius balls that are needed to cover . She then used these estimates to prove compressed-sensing bounds when the underlying sets have bounds on their covering numbers.

A key idea is that of closeness for a set. Say that and in the set are close if is small with high probability. This allows the union over more objects than one would naively expect—bad pun—and yields a recursive argument that gets strong bounds. The details are too complex to include here, so see her slides and work to get the details.

Eric Price: A Faster Fourier Transform On Sparse Data

The goal of “stable sparse recovery” or “compressive sensing” is to recover a -sparse approximation of a vector in from linear measurements of . This problem has a wide variety of applications, including streaming algorithms, image acquisition, and genetic testing. A related problem is that of computing a “sparse” Fourier transform, which approximates the Fast Fourier Transform in less than time. In this talk I will survey the results in the area and describe general techniques used in solving them.

The cost of computing the Fourier Transform is the main topic. And it is possible to reduce it from to sub-linear. That is the transform is computable without looking even at all the data, or the samples. The idea is to use that when the signal is sparse, at least approximately sparse, one can do much better than even . On real GPS location data, the speed-up is about a factor of , for example.

There are lots of previous results when the signals are very sparse. New results for the case of exact -sparseness get and similar results for noisy data.

To give an idea of how this works, let’s look at the case when the signal is -sparse. This case is done as follows:

Just take the first two terms , then divide and recover . The general exact- case follows by randomly reordering the data and using the above idea. They actually show how to recover an that is near the actual so that

is -sparse. Then they use a recursion and use the fact that

is linear.

The rest of talk was a survey at high level of compressed sensing—see the slides. One big difference here is that often the size of sample is more important than the speed of the algorithm. Think about MRIs: the samples require the huge machine to move, and given that computers are so fast, it is way more important to minimize the number of samples than the computing time.

A final problem was to consider some unknown sparse vector in dimensions. Assume we can get the inner product of for any . The question is, can we do better if allowed to be adaptive in selecting ? The answer is yes, in a way that saves and replaces a by a —and uses only samples. Clearly this is important when the cost of an experiment to get the inner product is expensive.

This was a fun and well-presented talk on results that combine great theory with potentially a variety of practical applications.

Swastik Kopparty: Polynomials and Complexity Theory

This tutorial will discuss some of the amazing and unexpected applications of polynomials in complexity theory.

This tutorial gave several applications of polynomials over a finite field. He first stated the basic properties of polynomials—for example, two polynomials of degree agree at most at points.

One application is the classic idea of secret sharing due to Adi Shamir. Example: I have a secret bit and want to give it to ten friends so that any two can reconstruct the secret, but no one can learn it alone. Let be a uniformly random polynomial of degree with . Then give each friend for different random . Then any two can reconstruct the polynomial, and thus get the secret. He then extended this to multi-party computation, and considered higher degrees.

His last application was to lower bounds on constant depth circuits. The main class is , I will omit the superscript of . They are constant-depth, polynomial size, and only have AND and OR’s. The main idea to see this proof is to use polynomials to approximate the steps of an circuit. The most interesting case is computing the OR function. Sasha Razaborov’s idea was to compute an OR by using random low degree polynomials. He went on to a result of his with Srikanth Srinivasan in which the circuits are augmented with parity gates.

This was a clear and neat talk. The only issue I take is that there are many many applications of polynomials that he did not even mention. Of course to do justice to even some fraction of the applications of polynomials would take a whole workshop. Indeed perhaps we should have one just on this topic.

Open Problems

The obvious suggestion is: when doing research, keep checking your problem, that is, your cheese. You may wish to move it and see if that leads to some new ideas.