Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's.

What's so special about MOD_m gates?

  • They allow one to simulate arithmetic over any ring Z_m.
  • Before Ryan's result, throwing MOD_m gates to the mix gave the first class for which the known lower bounds did not work.

Is there any other natural reason to study MOD_m gates?

share|improve this question
add comment

3 Answers 3

up vote 38 down vote accepted

$ACC^0$ is a natural complexity class.

1) Barrington showed that computation over non-solvable monoids capture $NC^1$ while over solvable monoids capture $ACC^0$.

2) Recently, Hansen and Koucky proved a beautiful result that poly-sized constant width planar branching programs are exactly $ACC^0$. Without the planarity condition, we of course get Barrington's result characterizing $NC^1$.

So the difference between $ACC^0$ and $NC^1$ is group-theoretic on one hand and topological on the other.

Added: Dana, a simple example of a solvable group is $S_4$, the symmetric group over elements. Without getting into details, any solvable group has a series whose quotients happen to be cyclic. This cyclic structure gets reflected as mod gates while building a circuit to solve word problems over the group.

On planarity, one would like to believe that planarity may impose restrictions/bottlenecks in the flow of information. This is not always true: for example, variations of planar 3SAT are known to be NP-complete. However, in smaller classes, these restrictions are more "likely" to hold.

In similar vein, Wigderson showed NL/poly=UL/poly using the isolation lemma. We do not know how to derandomize the isolation lemma over arbitrary DAGs to get NL=UL, but we know how to do so for planar DAGs.

share|improve this answer
1  
Thanks a lot for the information! I'd love to hear more about the intuition for these results. As to my question: your argument is basically that $NC^1$ [O(log n) depth, gates AND, OR, NOT] is natural, and $ACC$ is a slight variation of it (to solvable rather than non-solvable monoids, or to planar rather than non-planar branching programs). Could you elaborate a little: give examples of interesting monoids for computation, and how their solvability matters? Is there an a-priori motivation to take interest in whether a branching program is planar or not? –  Dana Moshkovitz Nov 9 '10 at 15:15
7  
To complement: 1) Computation over aperiodic monoids capture $AC^0$ (Barrington and Thérien). 2) Upward planar branching programs capture $AC^0$ (Barrington, Lu, Miltersen, Skyum). –  Kristoffer Arnsfelt Hansen Nov 9 '10 at 15:55
    
@Vinay: Are you sure that the result NL/poly=UL/poly is due to Wigderson? –  Dai Le Jul 8 '11 at 21:22
add comment

Perhaps this isn't really an answer to your question. But to just give one example of why sometimes $\bmod m$ gates (for composite $m$) are more powerful than $\bmod p$ gates:

Consider the class of constant depth circuits that consist only of $\bmod p$ gates, and inputs and constants at the leaves. Then, one can easily show that the OR function (for example) cannot be computed by such circuits, regardless of the size of the circuit. (This is because any such circuit computes a low degree polynomial over $\mathbb{F}_p$, and the degree of OR is $n$).

However, if we consider circuits that consist only of $\bmod m$ gates where $m$ has at least two distinct prime factors, there is a depth $2$ circuit (of exponential size) for the OR function.

And prior to Ryan's result, $AC^0[\bmod 6]$ was I guess the smallest class for which we didn't have any decent lower bounds.

share|improve this answer
1  
Addendum to the last sentence: It was already known that computing $MOD_q$ with constant-depth circuits using AND, OR, NOT, and $MOD_p$ gates for primes $p \ne q$ required an exponential number of gates. (There's an extension to relatively prime composites as well.) Since 6 is the smallest composite of two distinct primes, $MOD_6$ is the "easiest"-to-compute function that no exponential lower bound was known for. –  Daniel Apon Nov 10 '10 at 16:10
add comment

Just to elaborate on your two points:

If we are in the business of understanding computation, modular counting is one of the frontiers of our understanding. Modular counting is one of the simplest and most natural phenomena in computation, yet we seem to understand so little about it. We cannot rule out the possibility that polynomial size depth 3 circuits with just Mod6 gates can compute every function in NP. It is conjectured however that such circuits can only compute functions with large support size and hence cannot compute a very simple function like AND. At the upper bound side the situation is similar, we have no non-trivial results.

These questions are also very interesting from a purely mathematical perspective as they are closely linked to very natural questions about polynomials and matrices over Z_m. To give one example, we don't have good lower bounds for the rank of a nxn codiagonal matrix over Z_6. A codiagonal matrix has 0s on the diagonal and nonzeros off diagonal.

share|improve this answer
    
Those interested in "prime versus composite modulo" should check the home page of Vince Grolmusz: grolmusz.pitgroup.org –  Stasys Jul 7 '11 at 22:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.