BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/590
DTSTAMP:20230914T125930Z
SUMMARY:Constant Depth Circuit Complexity of Powering
DESCRIPTION:Speaker: Nikhil S Mande\n\nAbstract: \nAbstract: Boolean circui
t classes inherently capture the power of parallel computation\, and const
ant 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 polyno
mial sized Boolean circuit with unbounded fan-in AND and OR gates ($AC^0$)
\n\nA natural question is how the power of these circuits increase if we a
dd parity gates to them. Arithmetic over $\\mathbb{F}_{2^n}$ is naturall
y captured by this class since multiplication can be computed by small cir
cuits\, and addition by parity gates. One of the most basic arithmetic ope
rations is powering.\n\nIn this report\, we explore the complexity of comp
uting the $k$th power of an element $x \\in \\mathbb{F}_{2^n}$ by $AC^0$ c
ircuits equipped with parity gates. In particular\, we try to prove hard
ness in two cases\; one where the binary representation of the exponent lo
oks like a periodic string\, and the other where the exponent has large nu
mber of 0-1 alternations in its binary representation.\n
URL:https://www.tcs.tifr.res.in/web/events/590
DTSTART;TZID=Asia/Kolkata:20150318T161500
DTEND;TZID=Asia/Kolkata:20150318T171500
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR