Linear Equations Over Composite Moduli
A FOCS 2009 paper that sheds new light on the power of computation over composite moduli
Avi is one of the greatest complexity theorists in the world—-do I need to add Wigderson? He has done so much great work that it would take the entire post to even begin to list some of his contributions. As you probably know, he along with Omer Reingold, Salil Vadhan, just won the prestigious Gödel Prize for their brilliant work on the zig-zag product.
Today I would like to talk about recent work that he and Arkadev Chattopadhyay have done on one of my favorite general questions: understanding the power of computing over finite rings, not finite fields. Another simple way to say this is: what is the power of modular computations over composite moduli? We know very little about their power, and this in my opinion, is one of the great challenges we face in complexity theory.
I have many stories about Avi, but I thought I will share the story of his first published paper. At the time he was a graduate student, I was running a problem seminar. One problem that I discussed one day was on coloring graphs. Back then the following question was open: Let be a graph with vertices and assume that has a -coloring. If you restrict your algorithm to polynomial time, how many colors do you need? Then, we did not know about PCP methods, so for all we knew perhaps colors were enough?
I could prove that there was a polynomial time algorithm that used at most colors. This, had also been observed by others, and is really simple. Just break the vertices of into groups of size . Each group can be colored with colors, so try all colorings and in time exponential in you will find the coloring. Then, do the same for each group–using another set of colors. This uses colors and takes polynomial time, as long as is fixed.
Avi was attending my problem seminar. The next day he saw me and said that he had a polynomial time algorithm that used only colors. I was impressed, since I had thought hard about this problem. He then explained his algorithm, which was correct and quite neat. This was his first paper.
You may know his proof, but for those who do not here are the key ideas. Avi’s idea was to look at the degrees of the vertices of . If there is one vertex, say , with degree at least , then, its neighborhood is a bipartite graph–this uses that is colorable. So and all adjacent to it can be colored in colors. Remove them and continue. On the other hand, if all the degrees of the vertices are less than , then in this case use Brook’s Theorem:
Theorem: A graph with maximum vertex degree can be colored in at most colors.
This is a basic theorem in graph theory. Avi knew not only the theorem, but realized that it could be done in polynomial time. Like many graph theorems, the proof is constructive.
I think all and all a brilliant piece of work. I was impressed with Avi, and depressed that we all had missed such a beautiful argument.
The central problem is what is the power of modular computations. Computations over primes are reasonably well understood. That is not true for composite moduli. The reason that computations are harder to understand is based on the following simple fact:
Lemma: Let . If is a prime, then is equal to a polynomial modulo .
This is false for a composite. The fact that not all functions are polynomials destroys the technology that Alexander Razborov and Roman Smolensky developed, so brilliantly, for understanding circuits of constant depth with modular gates over a fixed prime.
One early result that shows the difference between prime and composite moduli is the beautiful work of David Barrington, Richard Beigel, Steven Rudich that showed that the degree of a polynomial that computed the OR function could be modulo . They actually prove much more, see their paper for details. The conventional wisdom is to expect better lower bounds technology in the future.
I cannot resist mentioning a result that is due to Nayantara Bhatnagar, Parikshit Gopalan, and myself. We show an equivalence between size of symmetric polynomials modulo composites and certain natural simultaneous communication protocols. This reduces the problem of proving bounds on the degree of symmetric polynomials to proving bounds on simultaneous communication protocols. Since communication bounds are often easier to understand, this equivalence helps explain the Barrington-Beigel-Rudich results. It also gives some new results. I may do a detailed post on this in the future.
The problem with our work is that it only works for symmetric polynomials. If the best way to compute some symmetric function is with a non-symmetric polynomial, then our method fails. Thus, one of the neat questions is: how much does the restriction to symmetric polynomials cost?
Linear Equations over Finite Rings
Avi and Arkadev Chattopadhyay have a wonderful paper that will appear in FOCS 2009. They have some new results on the lack of power of modular computation. They consider the constant depth (in fact depth 3) circuit family that has three layers: (i) the top gate is a majority gate, (ii) the next level gates are all gates, and (iii) the base gates are that can have arbitrary accepting sets.
As an aside they actually allow the “dual” family to by replacing all the gates by gates.
A word about “accepting sets.” Because the modular computations are over rings, one must allow arbitrary sets for acceptance. By this we mean that a modular gate works like this:
where is allowed to be any set. Again this is because not all functions are polynomials. Arkadev points out to me that no superlinear lower bounds exist for depth-two circuits when the gates have arbitrary accepting set.
Theorem: Let be co-prime integers such that is the product of two distinct primes. If is a type circuit that uses gates and computes , then the size of the circuit is .
I will not try to explain how they prove this result, please see their paper for that. However, I will try to give some idea of the proof. They are naturally led to the problem of understanding systems of equations of the form
where each are linear forms.
Let be the set of solutions to a system of equations of this form. They have to prove that there is an exponentially small correlation between the solution set and .
The easy direction is to see if this was false, then there could be a problem. Suppose that some system of linear equations correlated some with . Then, we might be able to amplify the correlation via the majority gate, so that it correlates well. This is not a proof, but I think this gives some motivation as to why such equations arise in their proof.
The complexity of such a system is because we are over a finite ring, and not a field. Thus, there is no Gaussian elimination available to help understand the system. Their attack is based on exponential sums, and uses several cool insights. Please take a look at the paper for details.
Their main theorem is restricted to moduli that are the products of two primes. Unless they have solved it already, an obvious open problem is what happens for three or more primes. Three is sometimes special: I still love Albert Meyer’s comment:
“Prove the theorem for and let go to infinity.”
Of course the other main question is what is the power of composite modular functions?
Also related: is there a theory of linear equations over finite rings? This could help with our understanding of modular computation, but would also be of independent interest.