神刀安全网

Progress On Modular Computation

New results on computing with modular gates

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- Progress On Modular Computation , size- Progress On Modular Computation Progress On Modular Computation circuit into a depth-2 circuit that is not too much larger in terms of Progress On Modular Computation as well as Progress On Modular Computation .

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 Progress On Modular Computation outputs Progress On Modular Computation if Progress On Modular Computation and Progress On Modular Computation otherwise. It is a simple computation: Add up the inputs modulo Progress On Modular Computation and see if the sum is Progress On Modular Computation . If so output Progress On Modular Computation , else output Progress On Modular Computation . This can be recognized by a finite-state automaton with Progress On Modular Computation states. It is not a complex computation by any means.

But there lurk in this simple operation Progress On Modular Computation some dark secrets. When Progress On Modular Computation is a prime the theory is fairly well understood. There remain some secrets but by Fermat’s Little Theorem a Progress On Modular Computation gate has the same effect as a polynomial. In general, when Progress On Modular Computation is composite, this is not true. This makes understanding Progress On Modular Computation 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 Progress On Modular Computation and Progress On Modular Computation .

Main Theorem

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

Theorem 1 There is an efficient algorithm that given an Progress On Modular Computation circuit of depth Progress On Modular Computation , input length Progress On Modular Computation , and size Progress On Modular Computation , outputs a depth-2 circuit of the form Progress On Modular Computation of size Progress On Modular Computation , where Progress On Modular Computation denotes some gate whose output depends only on the number of Progress On Modular Computation 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

Progress On Modular Computation

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

Progress On Modular Computation

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

Progress On Modular Computation

which is a polynomial that agrees with Progress On Modular Computation on Progress On Modular Computation .

Well, this is easy but brutish—and exponential size if Progress On Modular Computation is. The trick is to show that when Progress On Modular Computation 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 Progress On Modular Computation 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 Progress On Modular Computation be variables over the integers and let Progress On Modular Computation be relatively prime. Then there exist Progress On Modular Computation integral linear combinations Progress On Modular Computation of the variables and integer coefficients Progress On Modular Computation so that

Progress On Modular Computation

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

  1. The bound Progress On Modular Computation on the number of terms in the sum depends only on Progress On Modular Computation , not Progress On Modular Computation (or Progress On Modular Computation ); this may have other uses.
  2. The arithmetic of the sum is over an extension of Progress On Modular Computation to Progress On Modular Computation .
  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 Progress On Modular Computation 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 Progress On Modular Computation 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 thispost 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.

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Progress On Modular Computation

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址