Report on the recent Coding, Complexity, and Sparsity Workshop

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 ${N \times N}$ matrix in which ${N}$ 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
• 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

${\bullet }$ 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: ${O(n\log n)}$ time where ${n}$ 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 ${n}$? 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 ${k}$ sparse it possible to almost get the FFT in time linear in ${k}$. This is a huge improvement in many real-world situations.

${\bullet }$ 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.

${\bullet}$ Sylvester’s Problem: James Sylvester posed a problem that at first may seem just a curiosity for Victorian-era puzzle books: Given any ${N}$ 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 ${E_1,\dots,E_m}$ is bounded by

$\displaystyle \mathsf{Pr}[E_1] + \cdots + \mathsf{Pr}[E_m].$

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

$\displaystyle \sum_k X_k$

by

$\displaystyle \sum_k g_k X_k$

for suitably-chosen ${g_k}$ 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 ${T}$, this is defined as the number of ${\epsilon}$-radius balls that are needed to cover ${T}$. 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 ${s}$ and ${t}$ in the set are close if ${|X_s - X_t| }$ 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 ${K}$-sparse approximation ${x'}$ of a vector ${x}$ in ${\mathbb{R}^N}$ from ${M}$ linear measurements of ${x}$. 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 ${N \log N}$ 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 ${O(n\log n)}$ to sub-linear. That is the transform is computable without looking even at all the data, or the ${n}$ samples. The idea is to use that when the signal is sparse, at least approximately sparse, one can do much better than even ${n}$. On real GPS location data, the speed-up is about a factor of ${2}$, for example.

There are lots of previous results when the signals are very sparse. New results for the case of exact ${k}$-sparseness get ${O(k\log n)}$ and similar results for noisy data.

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

$\displaystyle x = (a,aw^{t},aw^{2t},\dots,aw^{nt}).$

Just take the first two terms ${a,aw^{t}}$, then divide and recover ${t}$. The general exact-${k}$ case follows by randomly reordering the data and using the above idea. They actually show how to recover an ${x'}$ that is near the actual ${x}$ so that

$\displaystyle x - x'$

is ${k/2}$-sparse. Then they use a recursion and use the fact that

$\displaystyle k/2 + k/4 + \cdots$

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 ${v}$ in ${n}$ dimensions. Assume we can get the inner product of ${v,x}$ for any ${x}$. The question is, can we do better if allowed to be adaptive in selecting ${x}$? The answer is yes, in a way that saves and replaces a ${\log}$ by a ${\log\log}$—and uses only ${O((k\log\log(n/k))}$ 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 ${d}$ agree at most at ${d}$ 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 ${P(x)}$ be a uniformly random polynomial of degree ${1}$ with ${P(0)=s}$. Then give each friend ${P(a_i)}$ for different random ${a_i}$. 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 ${\mathsf{AC}}$, I will omit the superscript of ${0}$. 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 ${\mathsf{AC}}$ 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 ${\epsilon>0}$ 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.

1. August 10, 2013 6:19 pm

“Who Moved My Cheese?” and the subsequent seminars were close to being the most stupid corporate concept to have passed through our world. Hopefully the books will all be burned along with the authors and enthusiasts, and replaced with your examples. Like building a church on the foundation of a pagan temple (ever been to Cuzco?)

August 12, 2013 2:15 pm

I agree.
Unfortunately the whole world economy is run by exploiting the mediocres, by those who are in power.

2. August 11, 2013 3:14 am

Dear Dick and Ken,

1. Am I moving the cheese of community TCS with my papers (http://www.andrebarbosa.eti.br/The_Cook-Levin_Theorem_is_False.pdf, http://arxiv.org/ftp/arxiv/papers/0907/0907.3965.pdf, http://www.andrebarbosa.eti.br/P_different_RP_Proof_Eng.pdf, http://www.andrebarbosa.eti.br/NP_is_not_in_P-Poly_Proof_Eng.pdf)?

2. Should hidden assumptions within the TCS continue occult , as those consider that the exponents of the polynomials (upon traditional classes P and NP) are always known and given?

3. Why computer scientists are so resistant to ideas so simple, ingenious and effective?

August 12, 2013 1:33 pm

Dick Lipton’s three examples of “cheese-moving problems” each are eminently practical; when we look for dual problems that reflect fundamental open problems, we are led (for example) to the Hodge Conjecture, in which

“The basic idea is to ask to what extent we can approximate the shape of a given object by gluing together simple geometric building blocks of increasing dimension. This technique turned out to be so useful that it got generalized in many different ways, eventually leading to powerful tools that enabled mathematicians to make great progress in cataloging the variety of objects they encountered in their investigations.”

It’s terrific to see to many urgent practical problems in engineering that are intimately linked to open problems in fundamental mathematics.

There is a nice quotation by David Mumford to this effect, an article Curves and their Jacobians (1975, that regrettably I cannot find on-line):

This subject [algebraic geometry] like all subjects, has a dual aspect in that all these abstract ideas would collapse of their own weight were it not for the underpinning supplied by concrete classical geometry. For me it has been a real adventure to perceive the interactions of all these aspects.

That is an adventure in which every 21st century STEM researcher can participate!

August 14, 2013 3:02 pm

Yet another cheese-moving essay is this week’s Huffington Post feature “The Coming Dark Age For Science In America.

Not much in the article will surprise any academic or industrial STEM researcher (the article’s subtitle is “Sequestration Ushers In A Dark Age For Science”). What *WAS* surprising (to me) was the 14,000 15,000 16,000++ comments. Those are numbers that every politician understands!

It’s evident (to everyone) that the American STEM community’s “cheese” has moved, and it’s evident too that the recent budget sequestration is (as it seems to me) not the proximate cause, but rather an direct effect, of that cheese-move.

So Dick and Ken are asking a mighty topical, mighty broad, mighty urgent question (as it seems to me), which is: Where’s the new cheese?

August 15, 2013 8:01 am

In regard to cheese-moving, since yesterday we have:

• 6,000+ new comments on Huffingtonpost (22,530 total)

• 1 new comment on GLL (2 total)

As usual in science, this large dimensionless ratio (6000/1) requires explanation:

Conjectures

▸ Senior complexity theorists are satisfied with their cheese?
▸ Junior complexity theorists are shy to speak-up in regard to cheese?
▸ The STEM community perceives CT as irrelevant to cheese?
▸ Institutions are focused on protecting their present cheese?
▸ No-one has good ideas in regard to finding new cheese?
▸ Everyone’s worried that they may not like the taste of new cheese?
▸ All of the above, and more?

• August 15, 2013 8:05 am

The distraction on my side is cheesy doings at what used to be spelled “chesse” :-(!

• September 5, 2013 12:59 pm

That, and their iceberg is melting!

August 30, 2013 8:15 pm

The final tally: 24,317 comments on HuffPost’s The Coming Dark Age For Science In America.

It is striking (and dismaying?) that research-grade STEM weblogs typically attract a dozen or two (too-often snarky) comments. The 1000-fold greater out-pouring of heartfelt comments on HuffPost suggests that the public is vastly hungry for better STEM narratives.