Chennai Mathematical Institute


11.30 am, Sminar Hall
A bit of arithmetic circuits : computation and complexity

Nikhil Balaji
Chennai Mathematical Institute.


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 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. 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 constant-size 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.