11.30 am, Sminar Hall A bit of arithmetic circuits : computation and complexity Nikhil Balaji Chennai Mathematical Institute. 130514 Abstract Division is a basic arithmetic operation. Many efficient algorithms(e.g. long division) are known for this problem 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. We will discuss this connection and show 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. Subject to time constraints, we will discuss the complexity of constantsize matrix powering and relate it to the question of whether the classic Sum of Square Roots problem admits a polynomial time algorithm (a long standing open problem) and discuss a (very weak) reduction to a special case of matrix powering. No special background on circuit complexity is required. Joint work with Eric Allender and Samir Datta.
