# Mathematics Colloquia and Seminars

### Efficient algorithm for nonnegative $C^2$ interpolation
Given a finite set $E \subset \mathbb{R}^2$ with $\#(E) = N$ and a function $f : E \to [0,\infty)$, how can we compute the order of magnitude of an optimal (in terms of the $C^2(\mathbb{R}^2)$ norm) nonnegative extension of $f$? In this talk, I will exhibit an efficient algorithm, that first preprocesses the set $E$ using $\mathcal{O}(N\log N)$ operations and $\mathcal{O}(N)$ storage, and then compute the optimal norm using $\mathcal{O}(N)$ operations.
We will investigate and improve the so-called Finiteness Principle'' for nonnegative interpolation, proven by Fefferman, Israel, and Luli, which reduces an $N$-dependent large optimization system to a collection of $N$-independent small subsystems. Then, using tools from combinatorial and computational geometry, we can reduce the number of such systems and identify them efficiently. If time permits, I will talk about the ideas behind the proof of the Finiteness Principle and the notion of sparsity" in representing an interpolant.