The classes of sums of arithmetic-geometric exponentials (SAGE) and of sums of nonnegative circuit polynomials (SONC) provide nonnegativity certificates which are based on the inequality of the arithmetic and geometric means. We study the cones of symmetric SAGE and SONC forms and their relations to the underlying symmetric nonnegative cone. As main results, we provide several symmetric cases where the SAGE or SONC property coincides with nonnegativity and we present quantitative results on the differences in various situations. The results rely on characterizations of the zeroes and the minimizers for symmetric SAGE and SONC forms, which we develop. Finally, we also study symmetric monomial mean inequalities and apply SONC certificates to establish a generalized version of Muirhead's inequality.

Given an $\mathcal{H}$-polytope $P$ and a $\mathcal{V}$-polytope $Q$, the decision problem of whether $P$ is contained in $Q$ is co-NP-complete. This hardness remains if $P$ is restricted to be a standard cube and $Q$ is restricted to be the affine image of a cross polytope. While this hardness classification by Freund and Orlin dates back to 1985, for general dimension there seems to be only limited progress on the decision problem so far. Based on a formulation of the problem in terms of a bilinear feasibility problem, we study sum of squares certificates to decide the containment problem. These certificates can be computed by a semidefinite hierarchy. As a main result, we show that under mild and explicitly known preconditions the semidefinite hierarchy converges in finitely many steps. In particular, if $P$ is contained in a large $\mathcal{V}$-polytope $Q$ (in a well-defined sense), then containment is certified by the first step of the hierarchy.

Let $g_1,\dots,g_k$ be tropical polynomials in n variables with Newton polytopes $P_1,\dots,\allowbreak P_k$. We study combinatorial questions on the intersection of the tropical hypersurfaces defined by $g_1,\dots,g_k$, such as the f-vector, the number of unbounded faces, and (in the case of a curve) the genus. Our point of departure is Vigeland's work [Tropical complete intersection curves, preprint, arXiv:math/0711.1962, 2007] which considered the special case $k=n-1$ and where all Newton polytopes are standard simplices. We generalize these results to arbitrary k and arbitrary Newton polytopes $P_1,\dots,P_k$. This provides new formulas for the number of faces and the genus in terms of mixed volumes. By establishing some aspects of a mixed version of Ehrhart theory we show that the genus of a tropical intersection curve equals the genus of a toric intersection curve corresponding to the same Newton polytopes.

(MATH) This note accompanies a video presentation on the use of homotopy methods for real-time visualizing a class of geometric tangent problems in $\RR3.

We investigate the enumerative geometry aspects of algorithmic line problems when the admissible bodies are balls or polytopes. For this purpose, we study the common tangent lines/transversals to k balls of arbitrary radii and 4-k lines in ${\mathbb R}^3$. In particular, we compute tight upper bounds for the maximum number of real common tangents/transversals in these cases. Our results extend the results of Macdonald, Pach, and Theobald who investigated common tangents to four unit balls in ${\mathbb R}^3$ [Discrete Comput. Geom., 26 (2001), pp. 1--17].

We propose a new algorithm, called linear sifting, for the optimization of decision diagrams that combines the efficiency of sifting and the power of linear transformations. The new algorithm is applicable to large examples, and in many cases leads to substantially more compact diagrams when compared to simple variable reordering. We also show in what sense linear transformations complement variable reordering and how the technique can be applied to verification issues. Going a step further, we discuss a synthesis scenario where-due to the complexity of the target function-it is inevitable to decompose the function in a preprocessing step. By using linear sifting it is possible to extract a linear filter and, hence, to achieve the necessary decomposition. Using this method we were able to synthesize functions with standard tools which fail otherwise.

In order to simplify a synthesis task for particularly hard functions it is sometimes inevitable to decompose the function in a preprocessing step. We propose a new algorithm for automatically decomposing a target function by extracting a linear filter within the synthesis process. The algorithm is an application of the Linear Sifting algorithm which has been proposed in Meinel et al. (1996). Using this method we were able to synthesize functions with standard tools which fail otherwise.

We propose a new algorithm, called linear sifting, for theoptimization of decision diagrams that combines the efficiency of sifting and the power of linear transformations. We show that the new algorithm is applicable to large examples, and that inmany cases it leads to substantiallymore compact diagrams when compared to simple variablereordering. We show inwhat sense linear transformationscomplement variable reordering, and we discuss applications of the new technique to synthesis and verification.