5
$\begingroup$

Define the $\newcommand{\MOD}{\text{MOD}}\MOD_q$ function from $\{0,1\}^n \rightarrow \{0,1\}$ as follows:

Let $x_1,\cdots,x_n$ be the input. Then $\MOD_q(x_1,\cdots,x_n)=0$ if the number of 1's in $x_1,\dots,x_n$ is divisible by $q$; $\MOD_q(x_1,\cdots,x_n)=1$ otherwise.

I want to compute $\MOD_4$ using a constant depth circuit using only the following gates: $\MOD_2$ gates and the usual AND, OR, NOT gates. Gate fan-in is unbounded. Technically I want to show that $\MOD_4 \in \text{ACC}_0[2]$, where $\text{ACC}_0[2]$ means alternating circuit of constant depth with parity gates ($\MOD_2$ counters). Or more generally, I want to show that $\MOD_{p^k} \in \text{ACC}_0[p]$.

Can this be done? Is there a way to compute $\MOD_4$ using $\MOD_2$, AND, OR, and NOT gates?

My attempt: If I pass the input through a $\MOD_2$ gate, then if it outputs 1 (i.e., odd) then $\MOD_4$ is also $= 1$. But $\MOD_2$ will output $0$ for the integers of the form $4k+2$ whereas $\MOD_4$ should be $1$ for those cases. I tried using OR, AND gates also but failed. I guess it will use some number theoretic property.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Hint: Compute running sums $y_i = x_1 \oplus \cdots \oplus x_i$; you want to know whether $y_n = 0$ and the number of times that the sequence $y_1,\ldots,y_n$ changed from 1 to 0 is even. $\endgroup$
    – Yuval Filmus
    Apr 22, 2016 at 11:22
  • $\begingroup$ @Raphael The question here is to show that MOD4 is in AC0[2], the class of uniform constant-depth circuits with parity gates ("I want to compute MOD4..."). It's a standard question in circuit complexity. You might be surprised that MOD3 is not in AC0[2]. So something is going on here. $\endgroup$
    – Yuval Filmus
    Apr 22, 2016 at 12:30
  • $\begingroup$ @Raphael, it's a standard question in Boolean circuit complexity. Explaining background will take a lot of time. I have read in Sanjeev Arora, Boaz Barak textbook that $MOD_p$ function cannot be computed using $MOD_q$ gates (besides AND, OR, NOT) , where $p, q$ are distinct primes. $\endgroup$
    – Pranav Bisht
    Apr 22, 2016 at 17:06
  • $\begingroup$ @YuvalFilmus Thanks for the nice hint! But how will I capture the flips in parity using a constant depth circuit. $\endgroup$
    – Pranav Bisht
    Apr 22, 2016 at 17:21
  • $\begingroup$ @PranavBisht Be resourceful. $\endgroup$
    – Yuval Filmus
    Apr 22, 2016 at 20:10

1 Answer 1

Reset to default
3
$\begingroup$

Suppose for simplicity that the number of ones in the input is even, and we want to know whether it is divisible by 4 or not. Intuitively, what we would like to do is to somehow "halve" the number of ones in the input; then divisible by 4 would correspond to even, and not divisible by 4 would correspond to odd. Since we have parity gates in our disposal, we would be able to solve our problem.

How do we "halve" the number of ones? The idea is to consider the running sums $$ y_i = x_1 \oplus \cdots \oplus x_i. $$ Each time $x_i = 1$, we have $y_{i+1} \neq y_i$. Half the time, $y_i$ switches from 0 to 1, and half the time it switches from 1 to 0. By concentrating on one-sided switches, we are able to effectively halve the number of ones, and so solve your problems. Details left to you.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I thought of following solution as per your construction: First at level 1, I will have $n$ parity gates each computing $y_i$. Then at level 2, for each pair $(y_i,y_{i+1})$ I will compute $y_i \wedge \overline{y_{i+1}}$ so as to compute number of transitions from 1 to 0. Then at third level, I will have a single parity taking as input, the output of ANDs of 2nd level. Finally at level 4, I will compute AND between $y_n$ and the output of parity gate at third level. (to check whether no of inputs were even at first place) $\endgroup$
    – Pranav Bisht
    Apr 24, 2016 at 5:39
  • 1
    $\begingroup$ That's right, this is how you implement it. It's not my construction, but rather taken from constant-depth periodic circuits by Howard Straubing. $\endgroup$
    – Yuval Filmus
    Apr 24, 2016 at 5:41
  • $\begingroup$ Just for curiosity would it have been better to ask this question on cs.theory.stackexchange? because they demand research level questions. $\endgroup$
    – Pranav Bisht
    Apr 24, 2016 at 5:45
  • $\begingroup$ No, your question would have been closed, since it's not research level. This site is the appropriate forum. $\endgroup$
    – Yuval Filmus
    Apr 24, 2016 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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