Sign Me Up: PosSLP, Sign Testing, and Polynomials

Given an integer, deciding its positivity may appear trivial initially. However, this problem becomes more compelling when the integer is presented in a compact form, as opposed to being explicitly represented as a bit string. One such way to represent numbers compactly is by using straight line programs and arithmetic circuits.

In this talk, I introduce the concept of straight line programs and subsequently introduce the PosSLP problem, which is the problem of testing the positivity of integers represented by straight line programs. Furthermore, I provide a brief survey of how PosSLP is connected to the Blum–Shub–Smale (BSS) model of computations over reals, numerical analysis, and other intriguing problems in complexity theory. To conclude the talk, I discuss our recent and ongoing research on the PosSLP problem.