Logical Approaches to Computational Barriers

Optimization and approximation problems related to polynomial system solving

Speaker:
| Klaus Meer |

We outline some current work in real number complexity theory with a focus on own results. The topics discussed are all located in the area of polynomial system solving. First, we concentrate on a combinatorial optimization problem related to homotopy methods for solving numerically generic polynomial systems. Then, approximation problems are discussed in relation with Probabilistically Checkable Proofs over the real numbers.

websites: Arnold Beckmann | 2006-04-20 |