Speaker: |
Nikhil S Mande |

Organiser: |
Nikhil S Mande |

Date: |
Wednesday, 18 Mar 2015, 16:15 to 17:15 |

Venue: |
D-405 (D-Block Seminar Room) |

(Scan to add to calendar)

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.