Progress On Modular Computation

Shiteng Chen and Periklis Papakonstaninou have just written an interesting paper on modular computation. Its title, “Depth Reduction for Composites,” means converting a depth-, size- circuit into a depth-2 circuit that is not too much larger in terms of as well as .

Today Ken and I wish to talk about their paper on the power of modular computation.

One of the great mysteries in computation, among many others, is: what is the power of modular computation over composite numbers? Recall that a gate outputs if and otherwise. It is a simple computation: Add up the inputs modulo and see if the sum is . If so output , else output . This can be recognized by a finite-state automaton with states. It is not a complex computation by any means.

But there lurk in this simple operation some dark secrets. When is a prime the theory is fairly well understood. There remain some secrets but by Fermat’s Little Theorem a gate has the same effect as a polynomial. In general, when is composite, this is not true. This makes understanding gates over composites much harder: simply because polynomials are easy to handle compared to other functions. As I once heard someone say:

“Polynomials are our friends.”

Chen and Papakonstaninou (CP) increase our understanding of modular gates by proving a general theorem about the power of low depth circuits with modular gates. This theorem is an exponential improvement over previous results when the depth is regarded as a parameter rather than constant. Their work also connects with the famous work of Ryan Williams on the relation between and .

Main Theorem

We will just state their main result and then state one of their key lemmas. Call a circuit of , , , and gates (for some ) an -circuit.

Theorem 1 There is an efficient algorithm that given an circuit of depth , input length , and size , outputs a depth-2 circuit of the form of size , where denotes some gate whose output depends only on the number of s in its input.

This type of theorem is a kind of normal-form theorem. It says that any circuit of a certain type can be converted into a circuit of a simpler type, and this can be done without too much increase in size. In complexity theory we often find that it is very useful to replace a complicated type of computational circuit with a much cleaner type of circuit even if the new circuit is bigger. The import of such theorems is not that the conversion can happen, but that it can be done in a manner that does not blow up the size too much.

This happens all through mathematics: finding normal forms. What makes computational complexity so hard is that the conversion to a simpler type often can be done easily—but doing so without a huge increase in size is the rub. For example, every map

can be easily shown to be equal to an integer-valued polynomial with coefficients in provided is a finite subset of . For every point , set

where the inner product is over the finitely many that appear in the -th place of some member of . Then is an integer and is the only nonzero value of on . We get

which is a polynomial that agrees with on .

Well, this is easy but brutish—and exponential size if is. The trick is to show that when is special in some way then the size of the polynomial is not too large.

Lemma 5

One of the key insights of CP is a lemma, Lemma 5 in their paper, that allows us to replace a product of many gates by a summation. We have changed variables in the statement around a little; see the paper for the full statement and context.

Lemma 5 Let be variables over the integers and let be relatively prime. Then there exist integral linear combinations of the variables and integer coefficients so that

The value of can be composite. The final modulus can be in place of and this helps in circuit constructions. Three points to highlight—besides products being replaced by sums—are:

1. The bound on the number of terms in the sum depends only on , not (or ); this may have other uses.

2. The arithmetic of the sum is over an extension of to .

3. The coefficients are integral. That is, the conclusion is doing more than just linearizing with complex coefficients, which as they remark in their proof would be easier. This also helps in building circuits where bits set to are being counted.

Further all of this can be done in a uniform way, so the lemma can be used in algorithms. This is important for their applications. Note this is a type of normal form theorem like we discussed before. It allows us to replace a product by a summation. The idea is that going from products to sums is often a great savings. Think about polynomials: the degree of a multi-variate polynomial is a often a better indicator of its complexity of a polynomial than its number of terms. It enables them to remove layers of large gates that were implementing the products (Lemma 8 in the paper) and so avoids the greatest source of size blowup in earlier constructions.

A final point is that the paper makes a great foray into mixed-modulus arithmetic, coupled with the use of exponential sums. This kind of arithmetic is not so “natural” but is well suited to building circuits. Ken once avoided others’ use of mixed-modulus arithmetic by introducing new variables—see the “additive” section of this post which also involves exponential sums.

Open Problems

The result of CP seems quite strong. I am, however, very intrigued by their Lemma 5. It seems that there should be other applications of this lemma. Perhaps we can discover some soon.