Algebra and Computation Seminar
2006.03.06 |
| Date | Thu Apr 06 |
| Time | 10:15 — 12:00 |
| Location | Aud. D3, Department of Math |
Title: On the complexity of numerical computation
Speaker: Peter Bro Miltersen
When: Thursday, March 30, 10:15-12:00
Where: Aud. D3, Department of Mathematical Sciences
Abstract
We study the problem PosSLP: Given a division-free straight-line program producing an integer N, decide whether N>0. We relate PosSLP to the Blum-Shub-Smale model of computation and we show that PosSLP essentially captures the problem of doing arbitrary-precision numerical computation. We show that the problemof computing the total degree of a multivariate polynomialgiven by a straight line program reduces to PosSLP. Then,using techniques derived from the construction of uniform constant-depth circuits for integer division by Hesse et al, we show that PosSlp lies in the counting hierarchy, CH.Combining our results with work of Tiwari, we show that the Euclidean Traveling Salesman Problem lies in CH - the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE.
Along the way, we encounter and discuss a very important problem in computational complexity of an algebraic flavour: Given two multi-variate artithmetic straight line programs (or even formula), decide if they denote the same polynomial. Anefficient Monte Carlo algorithm is known for this problem, but it is not known to be in P. It was recently shown by Impagliazzo and Kabanets that giving a non-trivial deterministic algorithm for this this problem is equivalent to proving non-trivial circuit lower bounds (in a sense that can be made precise and will be made precise during the talk).
Joint work with Eric Allender, Peter Burgisser and JohanKjeldgaard-Pedersen.