| Description |
Boolean circuit classes inherently capture the power of parallel computation, and constant depth circuits are a class of great interest. It is a classical result that the parity of $n$ bits cannot be computed by a constant depth polynomial sized Boolean circuit with unbounded fan-in AND and OR gates ($AC^0$)
A natural question is how the power of these circuits increase if we add parity gates to them. Arithmetic over $\mathbb{F}_{2^n}$ is naturally captured by this class since multiplication can be computed by small circuits, and addition by parity gates. One of the most basic arithmetic operations is powering.
In this report, we explore the complexity of computing the $k$th power of an element $x \in \mathbb{F}_{2^n}$ by $AC^0$ circuits equipped with parity gates. In particular, we try to prove hardness in two cases; one where the binary representation of the exponent looks like a periodic string, and the other where the exponent has large number of 0-1 alternations in its binary representation.
|