The circuit complexity of addition, subtraction, and multiplication has been well-understood for decades, but the complexity of division had remained something of a mystery. The first breakthough on the division problem occurred in the mid-1980's, when Beame, Cook, and Hoover showed that division can be computed by circuits of logarithmic depth (and in fact division can be computed by threshold circuits of depth O(1)). However, these circuits were somewhat difficult to construct -- and thus it remained an open question if division could be computed in logspace.

The second breakthrough occurred more recently, when Chiu, Davida, and Litow showed that division can be computed in logspace. The circuits that they produce were still not "easy" enough to construct, to be useful in certain applications. More formally, it was still not known if division could be computed in "uniform TC^0" (meaning that it was not known if division could be computed by threshold circuits of depth O(1) that are "very easy to construct").

I will report on joint work with Bill Hesse and David Mix Barrington, in which we resolve this question. The presentation will include a very simple division algorithm that can be implemented in logspace.