Sign Me Up: PosSLP, Sign Testing, and Polynomials

Prelegent(ci)

Gorav Jindal

Afiliacja

Max Planck Institute for Software Systems

Termin

24 kwietnia 2024 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---