Tuesday, January 31, 2006 4:30 pm 5130 Upson Hall Ioana Dumitriu University of California, Berkeley Toward accurate polynomial evaluation in rounded arithmetic Given a multivariate (real or complex) polynomial $p$ and a (real or complex) domain $\mathcal{D}$, we would like to decide if there is an algorithm that can evaluate $p$ accurately (i.e., with relative error less than $1$), using rounded (real or complex) "traditional model" arithmetic. We consider this problem both in the classical setting (where the operations are $+$, $-$, $\times$) and in a black-box setting (where other polynomial operations are allowed). We obtain necessary and sufficient conditions for $p$ to be accurately evaluable on $\mathcal{D}$ when $\mathcal{D} = \mathbb{R}^n$ or $\mathbb{C}^n$, and also for some smaller domains. I will also indicate progress toward constructing a complete decision procedure.