|
4:00 pm to 4:25 pm, Seminar Hall Division in Arithmetic circuits Nikhil Balaji Chennai Mathematical Institute. 20-08-14 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 Beame-Cook-Hoover(P-uniform NC^1), Reif and Tate(P-uniform TC^0), Chiu-Davidow-Litow(L-uniform NC^1), and culminating in the work of Hesse-Allender-Barrington(DLOGTIME-uniform 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 majority-depth. Given an arithmetic circuit representing a number, can you find the i-th 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.
|
