4:00 pm to 4:25 pm, Seminar Hall Division in Arithmetic circuits Nikhil Balaji Chennai Mathematical Institute. 200814 Abstract Division is a basic arithmetic operation. Many efficient algorithms for division (Euclid, long division) are known since antiquity. However, these algorithms are inherently sequential. What is the parallel complexity of division? There has been a long line of research aimed at pinning down the exact complexity of integer division starting with BeameCookHoover(Puniform NC^1), Reif and Tate(Puniform TC^0), ChiuDavidowLitow(Luniform NC^1), and culminating in the work of HesseAllenderBarrington(DLOGTIMEuniform TC^0). We revisit this question looking to optimize the algorithm in terms of *majority depth*(initially studied by Maciel and Therien). We present improved uniform TC^0 circuits for division, matrix powering, and related problems, where the improvement is in terms of majoritydepth. Given an arithmetic circuit representing a number, can you find the ith bit of the number? This problem (BitSLP) is closely related to the complexity of integer division. It is known that any improvements to the parallel complexity of division in terms of majority depth yields an improved algorithm for BitSLP. Coupled with our improved division algorithm, this yields an improvement in the complexity of BitSLP. Joint work with Eric Allender and Samir Datta.
